oj.uz

Submission #240642

# Submission time Handle Problem Language Result Execution time Memory
240642 2020-06-20T10:48:04 Z vanic Pictionary (COCI18_pictionary) C++14
140 / 140
 157 ms 23160 KB 
#include <math.h>
#include <cstdio>
#include <algorithm>
#include <vector>
 
using namespace std;
 
const int maxn=1e5+5, Log=17;

int n, m, q;
pair < int, int > parent[maxn];
int sz[maxn];
vector < pair < int, int > > ms[maxn];
int digni[maxn][Log];
int val[maxn][Log];
int dep[maxn];
 
 
int find(int x){
	if(parent[x].second==x){
		return x;
	}
	return find(parent[x].second);
}
 
void update(int x, int y, int val){
	x=find(x);
	y=find(y);
	if(sz[x]>sz[y]){
		swap(x, y);
	}
	parent[x]={val, y};
	sz[y]=max(sz[x]+1, sz[y]);
}

bool query(int x, int y){
	return find(x)==find(y);
}

void dfs(int x, int prosl, int d){
	digni[x][0]=prosl;
	dep[x]=d;
	for(int i=0; i<ms[x].size(); i++){
		if(ms[x][i].first!=prosl){
			val[ms[x][i].first][0]=ms[x][i].second;
			dfs(ms[x][i].first, x, d+1);
		}
	}
}

void precompute(){
	for(int i=1; i<Log; i++){
		for(int j=1; j<=n; j++){
			digni[j][i]=digni[digni[j][i-1]][i-1];
			val[j][i]=max(val[j][i-1], val[digni[j][i-1]][i-1]);
		}
	}
}

int izjed(int &x, int &y){
	int raz=dep[y]-dep[x];
	int sol=0;
	for(int i=0; i<Log; i++){
		if(raz & (1<<i)){
			sol=max(sol, val[y][i]);
			y=digni[y][i];
		}
	}
	return sol;
}

int lca(int x, int y){
	if(dep[x]>dep[y]){
		swap(x, y);
	}
	int sol=izjed(x, y);
	if(x==y){
		return sol;
	}
	for(int i=Log-1; i>-1; i--){
		if(digni[x][i]!=digni[y][i]){
			sol=max(sol, max(val[x][i], val[y][i]));
			x=digni[x][i];
			y=digni[y][i];
		}
	}
	sol=max(sol, max(val[x][0], val[y][0]));
	return sol;
}

int main(){
	scanf("%d%d%d", &n, &m, &q);
	for(int i=1; i<=n; i++){
		parent[i]={0, i};
	}
	int br=1;
	for(int i=0; i<m; i++){
		for(int j=(m-i)*2; j<=n; j+=m-i){
			if(!query(j, j-m+i)){
				update(j, j-m+i, br);
			}
		}
		br++;
	}
	int root;
	for(int i=1; i<=n; i++){
		if(parent[i].second!=i){
			ms[i].push_back({parent[i].second, parent[i].first});
			ms[parent[i].second].push_back({i, parent[i].first});
		}
		else{
			root=i;
		}
	}
	dfs(root, root, 0);
	precompute();
	int a, b;
	for(int i=0; i<q; i++){
		scanf("%d%d", &a, &b);
		printf("%d\n", lca(a, b));
	}
	return 0;
}

Compilation message

pictionary.cpp: In function 'void dfs(int, int, int)':
pictionary.cpp:43:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<ms[x].size(); i++){
               ~^~~~~~~~~~~~~
pictionary.cpp: In function 'int main()':
pictionary.cpp:92:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d", &n, &m, &q);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
pictionary.cpp:119:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &a, &b);
   ~~~~~^~~~~~~~~~~~~~~~
pictionary.cpp:115:5: warning: 'root' may be used uninitialized in this function [-Wmaybe-uninitialized]
  dfs(root, root, 0);
  ~~~^~~~~~~~~~~~~~~

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 2816 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 3072 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 3712 KB Output is correct
2 Correct 35 ms 3636 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 4088 KB Output is correct
2 Correct 48 ms 3960 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 7672 KB Output is correct
2 Correct 41 ms 7544 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 9336 KB Output is correct
2 Correct 60 ms 10100 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 12360 KB Output is correct
2 Correct 62 ms 12536 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 15344 KB Output is correct
2 Correct 124 ms 17112 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 18812 KB Output is correct
2 Correct 126 ms 20856 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 157 ms 23016 KB Output is correct
2 Correct 137 ms 23160 KB Output is correct