oj.uz

답안 #84072

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
84072 2018-11-12T17:21:38 Z thiago4532 Pictionary (COCI18_pictionary) C++17
0 / 140
 448 ms 28388 KB 
#include <bits/stdc++.h>
#define div divisores
 
using namespace std;
const int maxn = 1e5 + 10;
int pai[maxn], peso[maxn], ans[maxn];
 
int n, m, q;
 
int gcd(int a, int b){
	return b ? gcd(b, a%b) : a;
}
 
struct UnionFind{
	vector<int> pai, peso;
	int n;
 
	UnionFind(int n=0): n(n){
		init(n);
	}
 
	void init(int n){
		pai.resize(n+1);
		peso.resize(n+1);
 
		for(int i=1;i<=n;i++)
			pai[i] = i, peso[i] = 0;
	}
 
	int find(int u){
		return (pai[u] == u ? u : pai[u] = find(pai[u]));
	}
 
	inline void join(int a, int b){
		a = find(a);
		b = find(b);
 
		if(peso[a] == peso[b]) peso[b]++;
		else if(peso[a] > peso[b]) swap(a, b);
 
		pai[a] = b;
	}
};
 
struct query{
	int l, r, id;
};
vector<query> qq;
UnionFind uf[30];

void solve(vector<query>& queries, int ini, int fim, int nivel=0){
	int meio = (ini + fim) >> 1;
	for(int dia=ini;dia<=meio;dia++){
		int k = m - dia + 1;
		for(int i=2;i*k<=n;i++){
			if(uf[nivel].find(k) != uf[nivel].find(i*k)) uf[nivel].join(k, i*k);
		}
	}
	//cout << "Inserindo os caras de [" << ini << ", " << meio << "] no nivel " << nivel << "\n";
 
	vector<query> l, r;
	for(auto& q : queries){
		if(uf[nivel].find(q.l) == uf[nivel].find(q.r)) ans[q.id] = min(ans[q.id], fim), l.push_back(q);
		else r.push_back(q);
	}

    for(int dia=meio+1;dia<=fim;dia++){
        int k = m - dia + 1;
        for(int i=2;i*k<=n;i++){
            if(uf[nivel].find(k) != uf[nivel].find(i*k)) uf[nivel].join(k, i*k);
        }
    }

    for(auto& q : queries)
        if(uf[nivel].find(q.l) == uf[nivel].find(q.r)) ans[q.id] = min(ans[q.id], fim);

	if(ini == fim) return;
 
	solve(l, ini, meio, nivel+1);
	solve(r, meio+1, fim, nivel+1);
}	
 
int main(){
	//ios::sync_with_stdio(false), cin.tie(0);
	memset(ans, 0x3f, sizeof ans);
	cin >> n >> m >> q;
    for(int i=0;i<=20;i++)
        uf[i].init(n);

	for(int i=0;i<q;i++){
		int a, b;
		cin >> a >> b;
		qq.push_back({a, b, i});
	}
 
	// for(int k=m;k>=1;k--){
	// 	for(int i=2;i*k<=n;i++){
	// 		if(find(k) != find(i*k)) join(k, i*k);
	// 	}
 
	// 	for(int l=1;l<=q;l++){
	// 		if(marcado[l]) continue;
	// 		if(find(qq[l].first) == find(qq[l].second)) ans[l] = m - k + 1, marcado[l] = true;
	// 	}
	// }
	solve(qq, 1, m);
	for(int i=0;i<q;i++)
		cout << ans[i] << "\n";
	return 0;
}

Compilation message

pictionary.cpp: In function 'void solve(std::vector<query>&, int, int, int)':
pictionary.cpp:74:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
     for(auto& q : queries)
     ^~~
pictionary.cpp:77:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  if(ini == fim) return;
  ^~
pictionary.cpp: In function 'int main()':
pictionary.cpp:87:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
     for(int i=0;i<=20;i++)
     ^~~
pictionary.cpp:90:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  for(int i=0;i<q;i++){
  ^~~

Subtask #1
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 8 ms 1272 KB Output isn't correct

Subtask #2
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 22 ms 2752 KB Output isn't correct

Subtask #3
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 70 ms 8552 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 95 ms 11056 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 100 ms 11056 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 138 ms 11056 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 203 ms 15788 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 128 ms 16108 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 327 ms 22824 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 448 ms 28388 KB Output isn't correct
2 Halted 0 ms 0 KB -