oj.uz

Submission #786680

# Submission time Handle Problem Language Result Execution time Memory
786680 2023-07-18T11:12:22 Z qwerasdfzxcl JOI15_road_development (JOI15_road_development) C++17
10 / 100
 126 ms 30708 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

struct DSU{
	int path[100100];
	void init(int n){
		for (int i=1;i<=n;i++) path[i] = i;
	}

	int find(int s){
		if (s==path[s]) return s;
		return path[s] = find(path[s]);
	}

	bool merge(int s, int v){
		s = find(s), v = find(v);
		if (s==v) return false;
		path[v] = s;
		return true;
	}
}dsu;

struct Seg{
	int tree[400400], lazy[400400];

	void init(int i, int l, int r){
		lazy[i] = 0;
		if (l==r){tree[i] = 1; return;}

		int m = (l+r)>>1;
		init(i<<1, l, m); init(i<<1|1, m+1, r);
		tree[i] = tree[i<<1] + tree[i<<1|1];
	}

	void propagate(int i, int l, int r){
		if (lazy[i]) tree[i] = 0;
		else return;

		if (l!=r){
			lazy[i<<1] = 1;
			lazy[i<<1|1] = 1;
		}

		lazy[i] = 0;
		return;
	}

	void update(int i, int l, int r, int s, int e){
		propagate(i, l, r);
		if (r<s || e<l) return;
		if (s<=l && r<=e){
			lazy[i] = 1;
			propagate(i, l, r);
			return;
		}

		int m = (l+r)>>1;
		update(i<<1, l, m, s, e); update(i<<1|1, m+1, r, s, e);
		tree[i] = tree[i<<1] + tree[i<<1|1];
	}

	int query(int i, int l, int r, int s, int e){
		propagate(i, l, r);
		if (r<s || e<l) return 0;
		if (s<=l && r<=e) return tree[i];

		int m = (l+r)>>1;
		return query(i<<1, l, m, s, e) + query(i<<1|1, m+1, r, s, e);
	}
}tree;

vector<int> adj[100100], G[100100];
int dep[100100], par[100100], top[100100], sz[100100], in[100100], out[100100], cnt, n;
int T[100100], X[100100], Y[100100];

void dfs0(int s, int pa = 0){
	par[s] = pa;
	dep[s] = dep[pa] + 1;
	sz[s] = 1;
	for (auto &v:adj[s]) if (v!=pa){
		G[s].push_back(v);
		dfs0(v, s);

		sz[s] += sz[v];
	}
}

void dfs1(int s){
	in[s] = ++cnt;

	if (!G[s].empty()) swap(G[s][0], *max_element(G[s].begin(), G[s].end(), [&](int x, int y){
		return sz[x] < sz[y];
	}));
	
	for (auto &v:G[s]){
		if (v==G[s][0]) top[v] = top[s];
		else top[v] = v;
		dfs1(v);
	}

	out[s] = cnt;
}

int query(int x, int y, int t){
	// printf("query %d %d / %d %d / %d %d\n", x, y, in[x], in[y], top[x], top[y]);
	int ret = 0;

	while(top[x]!=top[y]){
		if (dep[top[x]] > dep[top[y]]) swap(x, y);
		ret += tree.query(1, 1, n, in[top[y]], in[y]);
		if (t==1) tree.update(1, 1, n, in[top[y]], in[y]);
		y = par[top[y]];
	}

	if (dep[x] > dep[y]) swap(x, y);
	// printf("ok %d to %d\n", in[x]+1, in[y]);
	ret += tree.query(1, 1, n, in[x]+1, in[y]);
	if (t==1) tree.update(1, 1, n, in[x]+1, in[y]);

	return ret;
}

int main(){
	int q;
	scanf("%d %d", &n, &q);

	dsu.init(n);
	for (int i=1;i<=q;i++){
		scanf("%d %d %d", T+i, X+i, Y+i);
		if (T[i]==1){
			if (dsu.merge(X[i], Y[i])){
				adj[X[i]].push_back(Y[i]);
				adj[Y[i]].push_back(X[i]);
			}
		}
	}

	vector<int> root;
	for (int i=1;i<=n;i++) if (!par[i]){
		root.push_back(i);
		dfs0(i);
	}

	for (auto &r:root){
		top[r] = r;
		dfs1(r);
	}

	tree.init(1, 1, n);

	dsu.init(n);
	for (int i=1;i<=q;i++){
		if (dsu.find(X[i])!=dsu.find(Y[i])){
			if (T[i]==2){
				printf("-1\n");
			}
			else{
				dsu.merge(X[i], Y[i]);
			}
		}

		else{
			int ans = query(X[i], Y[i], T[i]);
			if (T[i]==2) printf("%d\n", ans);
		}
	}
}

Compilation message

road_development.cpp: In function 'int main()':
road_development.cpp:127:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  127 |  scanf("%d %d", &n, &q);
      |  ~~~~~^~~~~~~~~~~~~~~~~
road_development.cpp:131:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  131 |   scanf("%d %d %d", T+i, X+i, Y+i);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5204 KB Output is correct
2 Correct 5 ms 5284 KB Output is correct
3 Correct 4 ms 5156 KB Output is correct
4 Correct 4 ms 5204 KB Output is correct
5 Correct 5 ms 5156 KB Output is correct
6 Correct 4 ms 5204 KB Output is correct
7 Correct 5 ms 5204 KB Output is correct
8 Correct 4 ms 5284 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 108 ms 30660 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 126 ms 30708 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 75 ms 15516 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5204 KB Output is correct
2 Correct 5 ms 5284 KB Output is correct
3 Correct 4 ms 5156 KB Output is correct
4 Correct 4 ms 5204 KB Output is correct
5 Correct 5 ms 5156 KB Output is correct
6 Correct 4 ms 5204 KB Output is correct
7 Correct 5 ms 5204 KB Output is correct
8 Correct 4 ms 5284 KB Output is correct
9 Runtime error 108 ms 30660 KB Execution killed with signal 11
10 Halted 0 ms 0 KB -