Submission #1117175

#TimeUsernameProblemLanguageResultExecution timeMemory
1117175mmkICC (CEOI16_icc)C++14
61 / 100
338 ms1276 KiB
#include<bits/stdc++.h> #include "icc.h" using namespace std; const int MAXN = 110; int pai[MAXN], marc[MAXN], sz[MAXN]; map<pair<int,int>,bool> aresta; // int query(int sza, int szb, int a[], int b[]); // int setRoad(int a, int b); // srand(time(0)); int q(vector<int> a, vector<int> b) { if(a.size() == 0 || b.size() == 0) return false; int sza = a.size(), szb = b.size(); for(int v : a) { for(int viz : b) if(aresta[{v,viz}]) return 1; } int novoA[sza], novoB[szb]; for(int i = 0; i < sza; i++) novoA[i] = a[i]; for(int i = 0; i < szb; i++) novoB[i] = b[i]; return query(sza, szb, novoA, novoB); } int find(int v) { if(pai[v] == v) return v; return pai[v] = find(pai[v]); } void un(int a, int b) { a = find(a); b = find(b); if(a == b) return; if(sz[a] < sz[b]) swap(a,b); pai[b] = a; sz[a] += sz[b]; } vector<int> botaGrupo(int v, int N) { vector<int> grupo; for(int i = 1; i <= N; i++) { if(find(i) == find(v)) grupo.push_back(i); } return grupo; } pair<vector<int>,vector<int>> split(vector<int> v, int N) { int sz = v.size(); int qtdA = 0, qtdB = 0; for(int i = 1; i <= N; i++) marc[i] = 0; vector<int> a,b; for(int i = 0; i < sz; i++) { if(marc[v[i]]) continue; int grupo = rand()%2; vector<int> adiciona = botaGrupo(v[i],N); if(qtdA >= sz/2) { for(int cur : adiciona) { marc[cur] = 1; b.push_back(cur); } qtdB++; } else if(qtdB >= sz/2) { for(int cur : adiciona) { marc[cur] = 1; a.push_back(cur); } qtdA++; } else { for(int cur : adiciona) { marc[cur] = 1; if(grupo == 0) a.push_back(cur); else b.push_back(cur); } if(grupo == 0) qtdA++; else qtdB++; } } return make_pair(a,b); } pair<vector<int>,vector<int>> split2(vector<int> v, int N) { int sz = v.size(); int qtdA = 0, qtdB = 0; vector<int> a,b; for(int i = 0; i < sz; i++) { int grupo = rand()%2; int cur = v[i]; if(qtdA >= sz/2) { b.push_back(cur); qtdB++; } else if(qtdB >= sz/2) { a.push_back(cur); qtdB++; } else { if(grupo == 0) a.push_back(cur); else b.push_back(cur); if(grupo == 0) qtdA++; else qtdB++; } } return make_pair(a,b); } pair<vector<int>,vector<int>> achaAresta(int N) { vector<int> todos; for(int i = 1; i <= N; i++) todos.push_back(i); pair<vector<int>,vector<int>> temp = split(todos,N); vector<int> a,b; a = temp.first, b = temp.second; // cerr << "grupo1: "; // for(int cur : a) cerr << cur << " "; // cerr << "\n"; // cerr << "grupo2: "; // for(int cur : b) cerr << cur << " "; // cerr << "\n"; vector<int> aux; if(q(a,b)) return {a,b}; else return {aux,aux}; } vector<int> achaGrupoPonta(vector<int> a, vector<int> b, int N) { vector<int> nulo; if(a.size() == 0 || b.size() == 0) return nulo; int grupoA = find(a[0]); bool mesmo = true; for(int cur : a) { if(find(cur) != grupoA) mesmo = false; } if(mesmo) return a; vector<int> half1, half2; pair<vector<int>,vector<int>> temp = split(a,N); half1 = temp.first, half2 = temp.second; if(q(half1,b)) return achaGrupoPonta(half1,b,N); else return achaGrupoPonta(half2,b,N); } int achaPonta(vector<int> a, vector<int> b, int N) { if(a.size() == 0) return -1; if(a.size() == 1) return a[0]; vector<int> half1,half2; pair<vector<int>,vector<int>> temp = split2(a,N); half1 = temp.first, half2 = temp.second; if(q(half1,b)) return achaPonta(half1,b,N); return achaPonta(half2,b,N); } void run(int N) { int cnt = N - 1; for(int i = 1; i <= N; i++) { pai[i] = i; sz[i] = 1; } while(cnt--) { bool achou = false; pair<vector<int>,vector<int>> aux; while(!achou) { // cerr << "bonga\n"; aux = achaAresta(N); if(aux.first.size() == 0 && aux.second.size() == 0) continue; else achou = true; } // vector<int> grupoA = achaGrupoPonta(aux.first,aux.second,N); // vector<int> grupoB = achaGrupoPonta(aux.second,aux.first,N); int pontaA = achaPonta(aux.first,aux.second,N); int pontaB = achaPonta(aux.second,aux.first,N); setRoad(pontaA,pontaB); un(pontaA,pontaB); aresta[{pontaA,pontaB}] = 1; aresta[{pontaB,pontaA}] = 1; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...