Submission #948834

#TimeUsernameProblemLanguageResultExecution timeMemory
948834phoenix0423ICC (CEOI16_icc)C++17
61 / 100
143 ms856 KiB
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<ll, ll> pll; #define fastio ios::sync_with_stdio(false), cin.tie(0) #define pb push_back #define eb emplace_back #define f first #define s second #define lowbit(x) x&-x #include "icc.h" const int maxn = 105; int n; int par[maxn]; int root(int x){ return x == par[x] ? x : par[x] = root(par[x]);} vector<int> comp[maxn]; set<pair<vector<int>, vector<int>>> used; bool qry(int sa, int sb, vector<int> a, vector<int> b){ int aa[a.size()], bb[b.size()]; copy(a.begin(), a.end(), aa), copy(b.begin(), b.end(), bb); return query(sa, sb, aa, bb); } void run(int _n){ n = _n; for(int i = 1; i <= n; i++) comp[i].pb(i), par[i] = i; random_device rd; mt19937 rng(rd()); for(int rd = 0; rd < n - 1; rd++){ used.clear(); set<int> st; for(int i = 1; i <= n; i++) st.insert(root(i)); vector<vector<int>> s(2); vector<vector<int>> id(2); bool c = false; while(!c){ s[0].clear(), s[1].clear(); for(auto x : st){ int cur = rng() % 2; id[cur].pb(x); for(auto u : comp[x]) s[cur].pb(u); } if(!s[0].size() || !s[1].size()) continue; if(used.count({id[0], id[1]}) || used.count({id[1], id[0]})) continue; used.insert({id[0], id[1]}); c = qry(s[0].size(), s[1].size(), s[0], s[1]); } int l = 0, r = s[0].size() - 1; while(l != r){ int m = (l + r) / 2; vector<int> ns; for(int i = l; i <= m; i++) ns.pb(s[0][i]); c = qry(ns.size(), s[1].size(), ns, s[1]); if(c) r = m; else l = m + 1; } vector<int> tmp(1, s[0][l]); swap(s[0], tmp); l = 0, r = s[1].size() - 1; while(l != r){ int m = (l + r) / 2; vector<int> ns; for(int i = l; i <= m; i++) ns.pb(s[1][i]); c = qry(1, ns.size(), s[0], ns); if(c) r = m; else l = m + 1; } setRoad(s[0][0], s[1][l]); int a = root(s[0][0]), b = root(s[1][l]); par[a] = b; for(auto x : comp[a]) comp[b].pb(x); } }
#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...