NC54830. 良心送分题
描述
输入描述
第一行数字
接下来行，每行两个数字
，表示树
中的一条边
接下来行，每行四个数字
，表示一条被添加的边
接下来一行四个数字。
输出描述
一行一个数字表示答案，若与
不连通则输出
示例1
输入:
4 4 3 1 2 1 3 3 4 1 2 2 2 1 3 3 1 2 3 3 2 3 2 3 4 1 2 3 4
输出:
5
C++14(g++5.4) 解法, 执行用时: 654ms, 内存消耗: 91740K, 提交时间: 2019-12-20 20:08:51
#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef long long LL;
typedef pair<int, int> P;
const int maxn = 2e5 + 5;
const int mod = 1e9 + 7;
vector<int> g[maxn];
int depth = 0, bn = 0, b[maxn << 1];
int f[maxn << 1],dfn[maxn], dis[maxn];
void dfs(int u, int fa) {
int tmp = ++depth;
b[++bn] = tmp;
f[tmp] = u;
dfn[u] = bn;
for (auto v:g[u]) {
if (v == fa) continue;
dis[v] = dis[u] + 1;
dfs(v, u);
b[++bn] = tmp;
}
}
int st[maxn << 1][20];
int lg[maxn << 1];
void st_init() {
for (int i = 2; i < maxn * 2; ++i) lg[i] = lg[i >> 1] + 1;
for (int i = bn; i >= 1; --i) {
st[i][0] = b[i];
for (int j = 1; i + (1 << j) - 1 <= bn; ++j)
st[i][j] = min(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
}
}
int rmq(int l, int r) {
int k = lg[r - l + 1];
return min(st[l][k], st[r - (1 << k) + 1][k]);
}
int lca(int a,int b) {
if(a == b) return a;
if (dfn[a] > dfn[b]) swap(a,b);
int k = rmq(dfn[a], dfn[b]);
return f[k];
}
vector<int> sd[maxn];
map<LL, int> hash_q;
int tot = 0, fs[maxn];
vector<P> sg[maxn * 2];
LL init_id;
int fhash(LL x) {
if(!hash_q.count(x)) hash_q[x] = ++tot;
return hash_q[x];
}
bool cmp(const int &i, const int &j) {
return dfn[i] < dfn[j];
}
int get_dis(int u, int v) {
int l = lca(u, v);
return dis[u] + dis[v] - dis[l] * 2;
}
void build_tree(int id, int n, vector<int> &vec) {
int sz = 0,k = vec.size();
sort(vec.begin(), vec.end(), cmp);
fs[sz] = 1;
for (int i = 0; i < k; ++i) {
int u = vec[i], ll = lca(u, fs[sz]);
if (ll == fs[sz]) fs[++sz] = u;
else {
while (sz >= 1 && dis[fs[sz - 1]] >= dis[ll]) {
int dd = get_dis(fs[sz], fs[sz - 1]);
sg[fhash(1LL * n * id + fs[sz - 1])].push_back(P(fhash(1LL * n * id + fs[sz]), dd));
sg[fhash(1LL * n * id + fs[sz])].push_back(P(fhash(1LL * n * id + fs[sz - 1]), dd));
sz--;
}
if (fs[sz] != ll) {
int dd = get_dis(fs[sz], ll);
sg[fhash(1LL * n * id + fs[sz])].push_back(P(fhash(1LL * n * id + ll), dd));
sg[fhash(1LL * n * id + ll)].push_back(P(fhash(1LL * n * id + fs[sz]), dd));
fs[sz] = ll;
}
fs[++sz] = u;
}
}
for (int i = 0; i < sz; ++i) {
int dd = get_dis(fs[i], fs[i + 1]);
sg[fhash(1LL * n * id + fs[i])].push_back(P(fhash(1LL * n * id + fs[i + 1]), dd));
sg[fhash(1LL * n * id + fs[i + 1])].push_back(P(fhash(1LL * n * id + fs[i]), dd));
}
}
LL D[maxn];
typedef pair<LL, int> PI;
set<PI> dq;
void dij(int st) {
for(int i = 1; i <= tot; ++i) D[i] = 1LL << 62;
D[st] = 0;
dq.insert(PI(0, st));
while(!dq.empty()) {
PI e = *dq.begin();
dq.erase(dq.begin());
int u = e.se;
LL w = e.fi;
for(auto ee:sg[u]) {
//cout<<u << " " << ee.fi << " - " << ee.se << endl;
if(D[ee.fi] > w + ee.se) {
dq.erase(PI(D[ee.fi], ee.fi));
D[ee.fi] = w + ee.se;
dq.insert(PI(D[ee.fi], ee.fi));
}
}
}
}
int main() {
int n, m, k, u, v, x, y;
scanf("%d%d%d", &n, &m, &k);
for(int i = 1; i < n; ++i) {
scanf("%d%d", &u, &v);
g[u].push_back(v);
g[v].push_back(u);
}
dis[1] = 0;
dfs(1, 0);
st_init();
for(int i = 0; i < m; ++i) {
scanf("%d%d%d%d", &u, &v, &x, &y);
sd[u].push_back(v);
sd[x].push_back(y);
u = fhash(1LL * u * n + v);
v = fhash(1LL * x * n + y);
sg[u].push_back(P(v, 1));
sg[v].push_back(P(u, 1));
}
scanf("%d%d%d%d", &u, &v, &x, &y);
sd[u].push_back(v);
sd[x].push_back(y);
u = fhash(1LL * u * n + v);
v = fhash(1LL * x * n + y);
init_id = 1LL * n * k;
for(int i = 1; i <= k; ++i) build_tree(i, n, sd[i]);
//for(auto e:hash_q) cout<<e.fi << " " << e.se<<endl;
dij(u);
//cout<<u<<" ??? " << v<<endl;
if(D[v] > 1e16) puts("-1");
else cout << D[v] << endl;
return 0;
}
C++(g++ 7.5.0) 解法, 执行用时: 650ms, 内存消耗: 94668K, 提交时间: 2022-11-19 15:59:38
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define endl '\n'
//#define int long long
#define fi first
#define se second
using namespace std;
typedef long long LL;
typedef pair<int, int> P;
const int maxn = 2e5 + 5;
const int mod = 1e9 + 7;
vector<int> g[maxn];
int depth = 0, bn = 0, b[maxn << 1];
int f[maxn << 1],dfn[maxn], dis[maxn];
void dfs(int u, int fa)
{
int tmp = ++depth;
b[++bn] = tmp;
f[tmp] = u;
dfn[u] = bn;
for (auto v:g[u])
{
if (v == fa) continue;
dis[v] = dis[u] + 1;
dfs(v, u);
b[++bn] = tmp;
}
}
int st[maxn << 1][20];
int lg[maxn << 1];
void st_init()
{
for (int i = 2; i < maxn * 2; ++i) lg[i] = lg[i >> 1] + 1;
for (int i = bn; i >= 1; --i)
{
st[i][0] = b[i];
for (int j = 1; i + (1 << j) - 1 <= bn; ++j)
st[i][j] = min(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
}
}
int rmq(int l, int r)
{
int k = lg[r - l + 1];
return min(st[l][k], st[r - (1 << k) + 1][k]);
}
int lca(int a,int b)
{
if(a == b) return a;
if (dfn[a] > dfn[b]) swap(a,b);
int k = rmq(dfn[a], dfn[b]);
return f[k];
}
vector<int> sd[maxn];
map<LL, int> hash_q;
int tot = 0, fs[maxn];
vector<P> sg[maxn * 2];
LL init_id;
int fhash(LL x)
{
if(!hash_q.count(x)) hash_q[x] = ++tot;
return hash_q[x];
}
bool cmp(const int &i, const int &j)
{
return dfn[i] < dfn[j];
}
int get_dis(int u, int v)
{
int l = lca(u, v);
return dis[u] + dis[v] - dis[l] * 2;
}
void build_tree(int id, int n, vector<int> &vec)
{
int sz = 0,k = vec.size();
sort(vec.begin(), vec.end(), cmp);
fs[sz] = 1;
for (int i = 0; i < k; ++i)
{
int u = vec[i], ll = lca(u, fs[sz]);
if (ll == fs[sz]) fs[++sz] = u;
else
{
while (sz >= 1 && dis[fs[sz - 1]] >= dis[ll])
{
int dd = get_dis(fs[sz], fs[sz - 1]);
sg[fhash(1LL * n * id + fs[sz - 1])].push_back(P(fhash(1LL * n * id + fs[sz]), dd));
sg[fhash(1LL * n * id + fs[sz])].push_back(P(fhash(1LL * n * id + fs[sz - 1]), dd));
sz--;
}
if (fs[sz] != ll)
{
int dd = get_dis(fs[sz], ll);
sg[fhash(1LL * n * id + fs[sz])].push_back(P(fhash(1LL * n * id + ll), dd));
sg[fhash(1LL * n * id + ll)].push_back(P(fhash(1LL * n * id + fs[sz]), dd));
fs[sz] = ll;
}
fs[++sz] = u;
}
}
for (int i = 0; i < sz; ++i)
{
int dd = get_dis(fs[i], fs[i + 1]);
sg[fhash(1LL * n * id + fs[i])].push_back(P(fhash(1LL * n * id + fs[i + 1]), dd));
sg[fhash(1LL * n * id + fs[i + 1])].push_back(P(fhash(1LL * n * id + fs[i]), dd));
}
}
LL D[maxn];
typedef pair<LL, int> PI;
set<PI> dq;
void dij(int st)
{
for(int i = 1; i <= tot; ++i) D[i] = 1LL << 62;
D[st] = 0;
dq.insert(PI(0, st));
while(!dq.empty())
{
PI e = *dq.begin();
dq.erase(dq.begin());
int u = e.se;
LL w = e.fi;
for(auto ee:sg[u])
{
//cout<<u << " " << ee.fi << " - " << ee.se << endl;
if(D[ee.fi] > w + ee.se)
{
dq.erase(PI(D[ee.fi], ee.fi));
D[ee.fi] = w + ee.se;
dq.insert(PI(D[ee.fi], ee.fi));
}
}
}
}
int main()
{
//IOS;
int n, m, k, u, v, x, y;
scanf("%d%d%d", &n, &m, &k);
for(int i = 1; i < n; ++i)
{
scanf("%d%d", &u, &v);
g[u].push_back(v);
g[v].push_back(u);
}
dis[1] = 0;
dfs(1, 0);
st_init();
for(int i = 0; i < m; ++i)
{
scanf("%d%d%d%d", &u, &v, &x, &y);
sd[u].push_back(v);
sd[x].push_back(y);
u = fhash(1LL * u * n + v);
v = fhash(1LL * x * n + y);
sg[u].push_back(P(v, 1));
sg[v].push_back(P(u, 1));
}
scanf("%d%d%d%d", &u, &v, &x, &y);
sd[u].push_back(v);
sd[x].push_back(y);
u = fhash(1LL * u * n + v);
v = fhash(1LL * x * n + y);
init_id = 1LL * n * k;
for(int i = 1; i <= k; ++i) build_tree(i, n, sd[i]);
//for(auto e:hash_q) cout<<e.fi << " " << e.se<<endl;
dij(u);
//cout<<u<<" ??? " << v<<endl;
if(D[v] > 1e16) puts("-1");
else cout << D[v] << endl;
return 0;
}
C++11(clang++ 3.9) 解法, 执行用时: 298ms, 内存消耗: 79056K, 提交时间: 2019-12-20 21:20:46
#include<map>
#include<set>
#include<cstdio>
#include<cctype>
#include<cstdlib>
#include<algorithm>
#define fi first
#define se second
#define F {puts("-1");exit(0);}
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
#define V(x,y) V[x][y]?V[x][y]:V[x][y]=++cnt
#define gc (p1==p2&&(p2=(p1=fr)+fread(fr,1,1<<21,stdin))==p1?EOF:*p1++)
using namespace std;
typedef pair<int,int> P;
char ch,fr[1<<21],*p1=fr,*p2=fr;
bool fig;
void rd(int&x)
{
while(!isdigit(ch=gc)&&ch^45); if(fig=ch==45)ch=gc;
x=ch-48;
while( isdigit(ch=gc)) x=ch-48+x*10;
if(fig) x=-x;
}
typedef long long ll;
const int N=21e5,M=2*N;
int n,m,k,u,v,to[M],ne[M],la[N],f[N/10][18],ti,dfn[N],dep[N],x,y,z,w,cnt,tot=1,To[M],Le[M],Ne[M],La[M],t,top,dis[N],c;
void dfs(int x)
{
dfn[x]=++ti, dep[x]=dep[f[x][0]]+1;
for(int i=1;f[x][i-1];i++) f[x][i]=f[f[x][i-1]][i-1];
for(int i=la[x],y;y=to[i];i=ne[i]) if(y^f[x][0]) f[y][0]=x,dfs(y);
}
map<int,int>V[51000];
map<int,int>::iterator it;
void link(int x,int y,int z)
{
To[++tot]=y,Le[tot]=z,Ne[tot]=La[x],La[x]=tot;
To[++tot]=x,Le[tot]=z,Ne[tot]=La[y],La[y]=tot;
}
void link(P x,P y) {link(x.se,y.se,dep[y.fi]-dep[x.fi]);}
P a[N],d[N];
bool vs[N];
bool cmp(P x,P y) {return dfn[x.fi]<dfn[y.fi];}
int LCA(int x,int y)
{
if(dep[x]<dep[y]) swap(x,y);
fd(i,17,0) if(dep[f[x][i]]>=dep[y]) x=f[x][i];
if(x==y) return x;
fd(i,17,0) if(f[x][i]^f[y][i]) x=f[x][i],y=f[y][i];
return f[x][0];
}
void ins(int i,P x)
{
if(top<2) {d[++top]=x; return;}
int lca=LCA(x.fi,d[top].fi);
if(lca^d[top].fi)
{
while(top>1&&dfn[d[top-1].fi]>=dfn[lca]) link(d[top-1],d[top]),top--;
if(lca^d[top].fi) link(P(lca,V(i,lca)),d[top]), d[top]=P(lca,V(i,lca));
}
d[++top]=x;
}
struct Comp{bool operator()(const P&a,const P&b){return a.se<b.se;}};
multiset<P,Comp> s;
int main()
{
rd(n),rd(m),rd(k);
fo(i,1,n-1)
{
rd(u),rd(v);
to[i*2 ]=v,ne[i*2 ]=la[u],la[u]=i*2 ;
to[i*2+1]=u,ne[i*2+1]=la[v],la[v]=i*2+1;
}
dfs(1);
fo(i,1,m)
{
rd(x),rd(y),rd(z),rd(w);
link(V(x,y),V(z,w),1);
}
rd(x),rd(y),rd(z),rd(w);
V(x,y); V(z,w);
fo(i,1,k)
{
V(i,1);
t=0;
for(it=V[i].begin();it!=V[i].end();it++) a[++t]=*it;
sort(a+1,a+t+1,cmp);
top=0;
fo(j,1,t)
ins(i,a[j]);
for(;top>1;top--) link(d[top-1],d[top]);
}
fo(i,1,cnt) dis[i]=0x7fffffff;
for(s.insert(P(V[x][y],dis[V[x][y]]=0));!s.empty();)
{
P t=*s.begin(); s.erase(s.begin());
if(dis[x=t.fi]<t.se) continue;
vs[x]=1;
for(int i=La[x],y;y=To[i];i=Ne[i]) if(dis[y]>(c=t.se+Le[i])) s.insert(P(y,dis[y]=c));
}
printf("%d",vs[x=V[z][w]]?dis[x]:-1);
}