제출 #1243514

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1243514		altern23	Pictionary (COCI18_pictionary)	C++20	140 / 140	195 ms	58588 KiB

pictionary

#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define pii pair<ll, ll>
#define fi first
#define sec second
#define ld long double

const int MAXN = 1e5;
const ll INF = 1e18;
const int MOD = 1e9 + 7;
const ld eps = 1e-6;	

struct DSU{
	ll N;
	vector<ll> par;
	DSU(ll _n){
		N = _n;
		par.resize(N + 5);
		for(int i = 1; i <= N; i++) par[i] = i;
	}
	ll find(ll idx){
		return (par[idx] == idx ? idx : par[idx] = find(par[idx]));
	}
	void join(ll a, ll b){
		a = find(a), b = find(b);
		if(a == b) return;
		par[b] = a;
	}
};

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);		
	int tc = 1;	
	// cin >> tc;
	for(;tc--;){
		ll N, M, Q; cin >> N >> M >> Q;
		vector<pair<pii, ll>> query[M + 5][2];
		vector<ll> lf(Q + 5), rg(Q + 5), ans(Q + 5);
		for(int i = 1; i <= Q; i++){
			ll a, b; cin >> a >> b;
			if(a != b){
				lf[i] = 1, rg[i] = M;
				query[(lf[i] + rg[i]) / 2][0].push_back({{a, b}, i});
			}
		}
		
		for(int log = 1; log < 20; log++){
			DSU dsu(N);
			for(int i = 1; i <= M; i++){
				for(int j = M - i + 1; j <= N; j += M - i + 1){
					dsu.join(M - i + 1, j);
				}
				for(auto [cur, idx] : query[i][(log % 2) ^ 1]){
					if(dsu.find(cur.fi) == dsu.find(cur.sec)){
						ans[idx] = i;
						rg[idx] = i - 1;
					}
					else lf[idx] = i + 1;
					if(lf[idx] <= rg[idx]){
						query[(lf[idx] + rg[idx]) / 2][log % 2].push_back({cur, idx});
					}
				}
				query[i][(log % 2) ^ 1].clear();
			}
		}
		
		for(int i = 1; i <= Q; i++) cout << ans[i] << "\n";
	}
}

• 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