Submission #786681

#	Time	Username	Problem	Language	Result	Execution time	Memory
786681		qwerasdfzxcl	도로 개발 (JOI15_road_development)	C++17	100 / 100	605 ms	31796 KiB

road_development

#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[300300], X[300300], Y[300300];

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 (stderr)

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 / 10
• Subtask 2: 25 / 25
• Subtask 3: 25 / 25
• Subtask 4: 25 / 25
• Subtask 5: 15 / 15