oj.uz

Submission #295041

# Submission time Handle Problem Language Result Execution time Memory
295041 2020-09-09T12:48:27 Z 임성재(#5809) JOI15_road_development (JOI15_road_development) C++14
0 / 100
 399 ms 24824 KB 
#include<bits/stdc++.h>
using namespace std;

#define fast ios::sync_with_stdio(false);
#define fi first
#define se second
#define em emplace
#define eb emplace_back
#define mp make_pair
#define all(v) (v).begin(), (v).end()

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int inf = 1e9;
const ll INF = 1e18;

struct UFT {
	int p[100010];

	void init(int k) {
		for(int i=1; i<=k; i++) p[i] = i;
	}

	int Find(int a) { return p[a] = p[a] == a ? a : Find(p[a]); }
	void Union(int a, int b) {
		if(Find(a) == Find(b)) {
			return;
		} 

		p[Find(b)] = Find(a); 
	}
} T[3];

int n, q, cnt;
int t[300010];
int a[300010];
int b[300010];

int sp[100010][21];

int L[100010], R[100010];
int d[100010];
vector<int> g[100010];
int tree[100010];
bool chk[100010];

void dfs(int x) {
	L[x] = ++cnt;

	for(int i=1; i<=20; i++) 
		sp[x][i] = sp[sp[x][i-1]][i-1];

	for(auto i : g[x]) {
		if(i == sp[x][0]) continue;

		d[i] = d[x] + 1;
		sp[i][0] = x;
		dfs(i);
	}

	R[x] = cnt;
}

int lca(int a, int b) {
	if(d[a] > d[b]) swap(a, b);

	for(int i=20; i>=0; i--) {
		if(d[b] - d[a] >= (1<<i)) b = sp[b][i];
	}

	if(a == b) return a;

	for(int i=2; i>=0; i--) {
		if(sp[a][i] != sp[b][i]) a = sp[a][i], b = sp[b][i];
	}

	return sp[a][0];
}

void update(int i, int x) {
	while(i <= n+1) {
		tree[i] += x;
		i += i & -i;
	}
}

int sum(int i) {
	int ret = 0;
	while(i) {
		ret += tree[i];
		i -= i & -i;
	}

	return ret;
}

int main() {
	fast;

	cin >> n >> q;

	T[0].init(n);

	for(int i=1; i<=q; i++) {
		cin >> t[i] >> a[i] >> b[i];

		if(t[i] == 2) continue;

		if(T[0].Find(a[i]) != T[0].Find(b[i])) {
			g[a[i]].eb(b[i]);
			g[b[i]].eb(a[i]);
			T[0].Union(a[i], b[i]);
		}
	}

	T[0].init(n);
	T[1].init(n);

	for(int i=1; i<=n; i++) {
		if(d[i]) continue;
		
		d[i] = 1;
		dfs(i);
	}

	for(int i=1; i<=n; i++) {
		update(L[i], 1);
		update(R[i]+1, -1);
	}

	for(int i=1; i<=q; i++) {
		if(t[i] == 1) {
			if(T[0].Find(a[i]) != T[0].Find(b[i])) {
				T[0].Union(a[i], b[i]);
			}
			else {
				a[i] = T[1].Find(a[i]);
				b[i] = T[1].Find(b[i]);
				
				while(a[i] != b[i]) {
					if(d[a[i]] < d[b[i]]) swap(a[i], b[i]);

					if(!chk[a[i]]) {
						update(L[a[i]], -1);
						update(R[a[i]]+1, 1);
						chk[a[i]] = true;
					}

					T[1].Union(sp[a[i]][0], a[i]);
					a[i] = T[1].Find(a[i]);
				}
			}
		}
		else {
			if(T[0].Find(a[i]) != T[0].Find(b[i])) cout << -1 << "\n";
			else cout << sum(L[a[i]]) + sum(L[b[i]]) - 2 * sum(L[lca(a[i], b[i])]) << "\n";
		}
	}
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2944 KB Output is correct
2 Correct 5 ms 2944 KB Output is correct
3 Incorrect 4 ms 2944 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 241 ms 20592 KB Output is correct
2 Correct 279 ms 20344 KB Output is correct
3 Correct 398 ms 23672 KB Output is correct
4 Correct 399 ms 24824 KB Output is correct
5 Correct 364 ms 23544 KB Output is correct
6 Correct 385 ms 23928 KB Output is correct
7 Incorrect 287 ms 21496 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 295 ms 20720 KB Output is correct
2 Incorrect 301 ms 20344 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 173 ms 19320 KB Output is correct
2 Correct 200 ms 19064 KB Output is correct
3 Correct 234 ms 21112 KB Output is correct
4 Correct 216 ms 23220 KB Output is correct
5 Correct 234 ms 20984 KB Output is correct
6 Correct 275 ms 24308 KB Output is correct
7 Incorrect 107 ms 18276 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2944 KB Output is correct
2 Correct 5 ms 2944 KB Output is correct
3 Incorrect 4 ms 2944 KB Output isn't correct
4 Halted 0 ms 0 KB -