Submission #83814

#	Time	Username	Problem	Language	Result	Execution time	Memory
83814		wzy	Pictionary (COCI18_pictionary)	C++11	140 / 140	108 ms	43096 KiB

pictionary

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

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 / 14
• Subtask 2: 14 / 14
• Subtask 3: 14 / 14
• Subtask 4: 14 / 14
• Subtask 5: 14 / 14
• Subtask 6: 14 / 14
• Subtask 7: 14 / 14
• Subtask 8: 14 / 14
• Subtask 9: 14 / 14
• Subtask 10: 14 / 14