Submission #400805

#	Time	Username	Problem	Language	Result	Execution time	Memory
400805		Plurm	Inside information (BOI21_servers)	C++11	2.50 / 100	380 ms	47064 KiB

servers

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

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
• Subtask 2: 0 / 2.5
• Subtask 3: 2.5 / 2.5
• Subtask 4: 0 / 2.5
• Subtask 5: 0 / 5
• Subtask 6: 0 / 5
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 12.5
• Subtask 10: 0 / 12.5
• Subtask 11: 0 / 17.5
• Subtask 12: 0 / 17.5