Submission #946638

#	Time	Username	Problem	Language	Result	Execution time	Memory
946638		MilosMilutinovic	도로 개발 (JOI15_road_development)	C++14	100 / 100	299 ms	27476 KiB

road_development

#include<bits/stdc++.h>
 
#define pb push_back
#define fi first
#define se second
#define mp make_pair
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef long double ld;
 
template <typename T> bool chkmin(T &x,T y){return x>y?x=y,1:0;}
template <typename T> bool chkmax(T &x,T y){return x<y?x=y,1:0;}
 
ll readint(){
	ll x=0,f=1; char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}

int n,q,tot,T;
int t[300005],a[300005],b[300005],fa[300005],v[200005],nxt[200005],h[100005],dep[100005],p[100005][20],fenw[200005],dfn[100005],dfo[100005];
bool was[100005];

void addedge(int x,int y){
	v[++tot]=y; nxt[tot]=h[x]; h[x]=tot;
	v[++tot]=x; nxt[tot]=h[y]; h[y]=tot;
}

int gfa(int x){return fa[x]==x?x:fa[x]=gfa(fa[x]);}

bool unite(int x,int y){
	x=gfa(x); y=gfa(y);
	if(x==y) return false;
	fa[y]=x;
	return true;
}

void dfs(int x,int f){
	dfn[x]=++T;
	dep[x]=dep[f]+1;
	p[x][0]=f;
	for(int i=1;i<20;i++) p[x][i]=p[p[x][i-1]][i-1];
	for(int p=h[x];p;p=nxt[p]){
		if(v[p]==f) continue;
		dfs(v[p],x);
	}
	dfo[x]=++T;
}

int lca(int x,int y){
	if(dep[x]>dep[y]) swap(x,y);
	for(int i=19;i>=0;i--) if(dep[p[y][i]]>=dep[x]) y=p[y][i];
	for(int i=19;i>=0;i--) if(p[x][i]!=p[y][i]) x=p[x][i],y=p[y][i];
	return x==y?x:p[x][0];
}

void change(int p,int x){
	for(;p<=200000;p+=p&-p) fenw[p]+=x;
}

int query(int p){
	int v=0;
	for(;p>=1;p-=p&-p) v+=fenw[p];
	return v;
}

int main(){
	n=readint(); q=readint();
	for(int i=1;i<=q;i++){
		t[i]=readint(); a[i]=readint(); b[i]=readint();
	}
	for(int i=1;i<=n;i++) fa[i]=i;
	for(int i=1;i<=q;i++){
		if(t[i]==2) continue;
		if(unite(a[i],b[i])){
			addedge(a[i],b[i]);
		}
	}
	for(int i=1;i<=n;i++) if(dep[i]==0) dfs(i,i);
	for(int i=1;i<=n;i++) fa[i]=i;
	for(int i=1;i<=q;i++){
		int l=lca(a[i],b[i]);
		if(t[i]==1){
			if(!unite(a[i],b[i])){
				for(int j=a[i];j!=l;j=p[j][0]){
					if(query(dfn[j])-query(dfn[l])==dep[j]-dep[l]){
						break;
					}
					int ver=j;
					for(int k=19;k>=0;k--){
						if(dep[p[ver][k]]>=dep[l]&&query(dfn[ver])-query(dfn[p[ver][k]])==dep[ver]-dep[p[ver][k]]) ver=p[ver][k];
					}
					if(ver==l) break;
					change(dfn[ver],+1);
					change(dfo[ver],-1);
					j=ver;
				}
				for(int j=b[i];j!=l;j=p[j][0]){
					if(query(dfn[j])-query(dfn[l])==dep[j]-dep[l]){
						break;
					}
					int ver=j;
					for(int k=19;k>=0;k--){
						if(dep[p[ver][k]]>=dep[l]&&query(dfn[ver])-query(dfn[p[ver][k]])==dep[ver]-dep[p[ver][k]]) ver=p[ver][k];
					}
					if(ver==l) break;
					change(dfn[ver],+1);
					change(dfo[ver],-1);
					j=ver;
				}
			}
			continue;
		}
		if(gfa(a[i])!=gfa(b[i])){
			printf("-1\n");
			continue;
		}
		printf("%d\n",dep[a[i]]+dep[b[i]]-2*dep[l]-(query(dfn[a[i]])+query(dfn[b[i]])-2*query(dfn[l])));
	}
	return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 25 / 25
• Subtask 3: 25 / 25
• Subtask 4: 25 / 25
• Subtask 5: 15 / 15