oj.uz

Submission #400805

# Submission time Handle Problem Language Result Execution time Memory
400805 2021-05-08T17:33:56 Z Plurm Inside information (BOI21_servers) C++11
2.5 / 100
 380 ms 47064 KB 
#include <bits/stdc++.h>
using namespace std;
vector<int> g[1 << 19];
int nodesz = 120005;
int newnode(){
	return ++nodesz;
}
int ptr[120005];
int par[1 << 19][20];
int dep[1 << 19];
void dfs(int u, int p = 0){
	dep[u] = dep[p]+1;
	par[u][0] = p;
	for(int i = 1; i < 20; i++){
		par[u][i] = par[par[u][i-1]][i-1];
	}
	for(int v : g[u]){
		dfs(v, u);
	}
}
int lca(int u, int v){
	if(dep[u] > dep[v]) swap(u, v);
	for(int i = 19; i >= 0; i--){
		if(dep[u] <= dep[par[v][i]]) v = par[v][i];
	}
	if(u == v) return u;
	for(int i = 19; i >= 0; i--){
		if(par[u][i] != par[v][i]){
			u = par[u][i];
			v = par[v][i];
		}
	}
	if(u == v) return u;
	return par[u][0];
}
int p[1 << 19];
int fn(int x){
	if(p[x] == -1) return x;
	else return p[x] = fn(p[x]);
}
int head[1 << 19];
void un(int x, int y, int z){
	x = fn(x);
	y = fn(y);
	if(x == y){
		head[x] = z;
		return;
	}
	p[x] = y;
	head[y] = z;
}
pair<int,int> bck[1 << 19];
int main(){
	memset(p, -1, sizeof(p));
	int n,k;
	scanf("%d%d",&n,&k);
	char cmd[2];
	for(int i = 1; i <= n; i++){
		ptr[i] = i;
		head[i] = i;
	}
	int nn;
	for(int i = 1; i < n+k; i++){
		scanf("%s", cmd);
		int x, y;
		switch(cmd[0]){
			case 'S':
				scanf("%d%d",&x,&y);
				nn = newnode();
				g[nn].push_back(head[fn(x)]);
				g[nn].push_back(head[fn(y)]);
				bck[nn] = make_pair(ptr[x], ptr[y]);
				un(x, y, nn);
				ptr[x] = nn;
				ptr[y] = nn;
				break;
			case 'Q':
				scanf("%d%d",&x,&y);
				break;
			case 'C':
				scanf("%d",&x);
				break;
		}
	}
	dfs(nodesz);
	fseek(stdin, 0, SEEK_SET);
	scanf("%d%d",&n,&k);
	for(int i = 1; i <= n; i++){
		ptr[i] = i;
	}
	nodesz = 120005;
	for(int i = 1; i < n+k; i++){
		scanf("%s", cmd);
		int x, y;
		switch(cmd[0]){
			case 'S':
				scanf("%d%d",&x,&y);
				nn = newnode();
				ptr[x] = nn;
				ptr[y] = nn;
				break;
			case 'Q':
				scanf("%d%d",&x,&y);
				x = ptr[x];
				if(x >= 120005 && (lca(bck[x].first, y) == bck[x].first || lca(bck[x].second, y) == bck[x].second)){
					printf("yes\n");
				}else{
					printf("no\n");
				}
				break;
			case 'C':
				scanf("%d",&x);
				printf("%d\n", dep[x] - dep[ptr[x]]);
				break;
		}
	}
	return 0;
}

Compilation message

servers.cpp: In function 'int main()':
servers.cpp:56:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   56 |  scanf("%d%d",&n,&k);
      |  ~~~~~^~~~~~~~~~~~~~
servers.cpp:64:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   64 |   scanf("%s", cmd);
      |   ~~~~~^~~~~~~~~~~
servers.cpp:68:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   68 |     scanf("%d%d",&x,&y);
      |     ~~~~~^~~~~~~~~~~~~~
servers.cpp:78:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   78 |     scanf("%d%d",&x,&y);
      |     ~~~~~^~~~~~~~~~~~~~
servers.cpp:81:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   81 |     scanf("%d",&x);
      |     ~~~~~^~~~~~~~~
servers.cpp:87:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   87 |  scanf("%d%d",&n,&k);
      |  ~~~~~^~~~~~~~~~~~~~
servers.cpp:93:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   93 |   scanf("%s", cmd);
      |   ~~~~~^~~~~~~~~~~
servers.cpp:97:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   97 |     scanf("%d%d",&x,&y);
      |     ~~~~~^~~~~~~~~~~~~~
servers.cpp:103:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  103 |     scanf("%d%d",&x,&y);
      |     ~~~~~^~~~~~~~~~~~~~
servers.cpp:112:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  112 |     scanf("%d",&x);
      |     ~~~~~^~~~~~~~~

Subtask #1
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 110 ms 15040 KB Output is correct
2 Incorrect 130 ms 17256 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 110 ms 15040 KB Output is correct
2 Incorrect 130 ms 17256 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 98 ms 15072 KB Output is correct
2 Correct 380 ms 47064 KB Output is correct
3 Correct 377 ms 47040 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 98 ms 15072 KB Output is correct
2 Correct 380 ms 47064 KB Output is correct
3 Correct 377 ms 47040 KB Output is correct
4 Incorrect 95 ms 15876 KB Extra information in the output file
5 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

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

Subtask #6
0 / 5.0

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

Subtask #7
0 / 10.0

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

Subtask #8
0 / 10.0

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

Subtask #9
0 / 12.5

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

Subtask #10
0 / 12.5

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

Subtask #11
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 107 ms 15056 KB Output is correct
2 Incorrect 137 ms 17288 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 107 ms 15056 KB Output is correct
2 Incorrect 137 ms 17288 KB Output isn't correct
3 Halted 0 ms 0 KB -