Submission #1215567

#TimeUsernameProblemLanguageResultExecution timeMemory
1215567dostsFountain Parks (IOI21_parks)C++20
0 / 100
3594 ms48948 KiB
#include "parks.h" #include <bits/stdc++.h> #pragma GCC optimize("O3,unroll-loops") #pragma GCC target("avx2") //#define int long long #define pii pair<int,int> #define vi vector<int> #define ff first #define ss second #define sp << " " << #define all(x) x.begin(),x.end() #define big(x) ((int)(x.size())) using namespace std; const int MOD = 1e9+7, LIM = 1e6+1, inf = 2e9; struct DSU { vi dad; DSU(){} DSU(int nn) { dad.resize(nn); for (int i =0 ;i<nn;i++) dad[i] = i; } int find(int x) { if (x == dad[x]) return x; return dad[x] = find(dad[x]); } bool unite(int a,int b) { int x = find(a),y = find(b); if (x == y) return false; dad[x] = y; return true; } } dsu; vi x,y; bool tryout(vector<pii> edgs) { int n = edgs.size(); set<pii> benches[n]; map<pii,vi> useful; for (int i = 0;i<n;i++) { auto it = edgs[i]; pii p1 = {x[it.ff],y[it.ff]}; pii p2 = {x[it.ss],y[it.ss]}; if (p1.ff == p2.ff) { benches[i] = {{p1.ff-1,max(p1.ss,p2.ss)-1},{p1.ff+1,max(p1.ss,p2.ss)-1}}; } else { benches[i] = {{max(p1.ff,p2.ff)-1,p1.ss-1},{max(p1.ff,p2.ff)-1,p1.ss+1}}; } for (auto it : benches[i]) useful[it].push_back(i); } vi done(n,0); vi u(n),v(n),a(n,-1),b(n,-1); for (int i = 0;i<n;i++) u[i] = edgs[i].ff,v[i] = edgs[i].ss; while (1) { int fnd = -1; for (int i = 0;i<n;i++) { if (!done[i] && big(benches[i]) == 1) { fnd = i; } } if (fnd != -1) { done[fnd] = 1; pii assign = *benches[fnd].begin(); a[fnd] = assign.ff,b[fnd] = assign.ss; for (auto it : useful[assign]) benches[it].erase(assign); continue; } for (int i = 0;i<n;i++) { if (!done[i] && big(benches[i]) == 2) { fnd = i; } } if (fnd == -1) break; done[fnd] = 1; pii assign = *benches[fnd].begin(); a[fnd] = assign.ff,b[fnd] = assign.ss; for (auto it : useful[assign]) benches[it].erase(assign); continue; } for (int i = 0;i<n;i++) if (a[i] == -1 || b[i] == -1) return false; build(u,v,a,b); return true; } int construct_roads(std::vector<int> xx, std::vector<int> yy) { x = xx,y = yy; int n = x.size(); if (x.size() == 1) { build({}, {}, {}, {}); return 1; } map<pii,int> id; for (int i = 0;i<n;i++) { id[{x[i],y[i]}] = i; } vi dx{2,0,-2,0},dy{0,2,0,-2}; dsu = DSU(n); int con = 0; vector<pii> edgs; for (int i = 0;i<n;i++) { for (int j = 0;j<4;j++){ if (id.count({x[i]+dx[j],y[i]+dy[j]})) { if (dsu.unite(i,id[{x[i]+dx[j],y[i]+dy[j]}])) { con++; edgs.push_back({i,id[{x[i]+dx[j],y[i]+dy[j]}]}); } } } } if (con < n-1) return 0; if (tryout(edgs)) return 1; return 0; }
#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...