oj.uz

Submission #83814

# Submission time Handle Problem Language Result Execution time Memory
83814 2018-11-11T02:58:23 Z wzy Pictionary (COCI18_pictionary) C++11
140 / 140
 108 ms 43096 KB 
#include <bits/stdc++.h>
using namespace std;
const int N = 1000005;
int pai[N] , peso[N] , tempo[N] , depth[N];
vector<int> adj[N];
bool vis[N];
int fd(int x){
	return pai[x] == x ? x : fd(pai[x]);
}

void join(int u , int v , int tmp){
	u = fd(u) , v = fd(v);
	if(peso[u] < peso[v]) swap(u,v);
	adj[u].push_back(v);
	adj[v].push_back(u);
	pai[v] = u , peso[u] += peso[v] , tempo[v] = tmp;
}

void dfs(int x , int p){
	vis[x] = true;
	if(x == p) depth[x] = 1;
	else depth[x] = depth[p] + 1;
	for(auto w : adj[x]){
		if(w == p || vis[w]) continue;
		dfs(w,x);
	}
}

int32_t main(){
	int n , m , q;
	scanf("%d%d%d"  , &n , &m , &q);
	for(int i = 1 ; i <= n; i ++) pai[i] = i, tempo[i] = N + 100 , peso[i] = 1;
	for(int i = m ; i >= 1 ; i--){
		for(int j = 2*i ; j <= n ; j+=i){
			if(fd(i) != fd(j))
			join(i, j , m - i + 1);
		}
	}
	for(int i = 1 ; i <= n; i ++){
		if(!vis[fd(i)]) dfs(fd(i) , fd(i));
	}
	while(q--){
		int x,y;
		scanf("%d%d" , &x , &y);
		if(depth[x] > depth[y]) swap(x,y);
		int ans = -100;
		while(depth[y] > depth[x]){
			ans = max(ans , tempo[y]);
			y = pai[y];
		}
		while(x != y){
			ans = max(ans , max(tempo[x] , tempo[y]));
			x = pai[x] , y = pai[y];
		}
		printf("%d\n" , ans);
	}
}

Compilation message

pictionary.cpp: In function 'int32_t main()':
pictionary.cpp:31: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:44:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d" , &x , &y);
   ~~~~~^~~~~~~~~~~~~~~~~~

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 23928 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 24228 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 25116 KB Output is correct
2 Correct 48 ms 25576 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 26672 KB Output is correct
2 Correct 57 ms 27512 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 28956 KB Output is correct
2 Correct 49 ms 29516 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 30508 KB Output is correct
2 Correct 54 ms 31468 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 32896 KB Output is correct
2 Correct 62 ms 33436 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 35272 KB Output is correct
2 Correct 87 ms 36716 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 38340 KB Output is correct
2 Correct 94 ms 40104 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 41908 KB Output is correct
2 Correct 108 ms 43096 KB Output is correct