oj.uz

Submission #295138

# Submission time Handle Problem Language Result Execution time Memory
295138 2020-09-09T13:45:12 Z 송준혁(#5805) JOI15_road_development (JOI15_road_development) C++14
0 / 100
 423 ms 25720 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define INF (1ll<<62)
#define MOD 1'000'000'007
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;

int N, Q, ans;
int T[303030], U[303030], V[303030];
int Pa[101010], P[101010][20], D[101010];
int nx[101010];
bool chk[101010];
vector<int> adj[101010];

int rt(int u){
	if (u == Pa[u]) return u;
	return Pa[u] = rt(Pa[u]);
}

void dfs(int u, int p){
	D[u] = D[p]+1, P[u][0] = nx[u] = p, chk[u] = true;
	for (int i=1; i<=18; i++) P[u][i] = P[P[u][i-1]][i-1];
	for (int v : adj[u]) if (v != p) dfs(v, u);
}

int lca(int u, int v){
	if (D[u] > D[v]) swap(u, v);
	for (int i=18; i>=0; i--) if (D[u] <= D[v] - (1<<i)) v = P[v][i];
	if (u == v) return u;
	for (int i=18; i>=0; i--) if (P[u][i] != P[v][i]) u = P[u][i], v = P[v][i];
	return P[u][0];
}

int up(int u, int r){
	if (D[u] <= D[r]) return u;
	if (chk[u]) ans++, chk[u]=false;
	return nx[u] = up(nx[u], r);
}

int main(){
	scanf("%d %d", &N, &Q);
	for (int i=1; i<=N; i++) Pa[i] = i;
	for (int i=1; i<=Q; i++){
		scanf("%d %d %d", &T[i], &U[i], &V[i]);
		if (T[i] == 1 && rt(U[i]) != rt(V[i])){
			adj[U[i]].pb(V[i]), adj[V[i]].pb(U[i]);
			Pa[rt(U[i])] = rt(V[i]);
		}
	}
	for (int i=1; i<=N; i++) if (!D[i]) dfs(i, 0);
	for (int i=1; i<=N; i++) Pa[i] = i;
	for (int i=1; i<=Q; i++){
		if (rt(U[i]) != rt(V[i])){
			if (T[i] == 1) Pa[rt(U[i])] = rt(V[i]);
			else puts("-1");
		}
		else{
			ans = 0;
			up(U[i], lca(U[i], V[i]));
			up(V[i], lca(U[i], V[i]));
			if (T[i] == 2) printf("%d\n", ans);
		}
	}
	return 0;
}

Compilation message

road_development.cpp: In function 'int main()':
road_development.cpp:44:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   44 |  scanf("%d %d", &N, &Q);
      |  ~~~~~^~~~~~~~~~~~~~~~~
road_development.cpp:47:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   47 |   scanf("%d %d %d", &T[i], &U[i], &V[i]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

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

Subtask #2
0 / 25.0

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

Subtask #3
0 / 25.0

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

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 188 ms 20440 KB Output is correct
2 Correct 234 ms 20216 KB Output is correct
3 Correct 309 ms 22264 KB Output is correct
4 Correct 303 ms 23288 KB Output is correct
5 Correct 317 ms 22524 KB Output is correct
6 Correct 423 ms 25720 KB Output is correct
7 Incorrect 108 ms 17656 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

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