Submission #1217734

#TimeUsernameProblemLanguageResultExecution timeMemory
1217734guagua0407Fountain Parks (IOI21_parks)C++20
5 / 100
289 ms37148 KiB
#include "parks.h" //#include "grader.cpp" #include <bits/stdc++.h> using namespace std; #define ll long long #define pii pair<int,int> #define f first #define s second #define all(x) x.begin(),x.end() #define _ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); namespace{ struct DSU{ vector<int> e; DSU(int n){ e=vector<int>(n,-1); } int find(int x){ return (e[x]<0?x:e[x]=find(e[x])); } int sz(int x){ return -e[find(x)]; } bool unite(int a,int b){ a=find(a); b=find(b); if(a==b) return false; if(e[a]>e[b]) swap(a,b); e[a]+=e[b]; e[b]=a; return true; } }; } int construct_roads(std::vector<int> x, std::vector<int> y) { map<int,map<int,int>> mp; int n=(int)x.size(); for(int i=0;i<n;i++){ mp[y[i]][x[i]]=i+1; } vector<int> u,v,a,b; for(int i=0;i<n;i++){ if(mp[y[i]+2][x[i]]!=0){ u.push_back(i); v.push_back(mp[y[i]+2][x[i]]-1); if(y[i]%4==0){ a.push_back(x[i]-1); b.push_back(y[i]+1); } else{ a.push_back(x[i]+1); b.push_back(y[i]+1); } } if(mp[y[i]][x[i]+2]!=0){ u.push_back(i); v.push_back(mp[y[i]][x[i]+2]-1); if(x[i]%4==0){ a.push_back(x[i]+1); b.push_back(y[i]-1); } else{ a.push_back(x[i]+1); b.push_back(y[i]+1); } } } DSU dsu(n); for(int i=0;i<(int)u.size();i++){ dsu.unite(u[i],v[i]); } if(dsu.sz(0)!=n) return 0; build(u,v,a,b); return 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...