제출 #468561

#제출 시각아이디문제언어결과실행 시간메모리
468561fun_day분수 공원 (IOI21_parks)C++17
5 / 100
1400 ms77436 KiB
#include <bits/stdc++.h> #include "parks.h" using namespace std; struct Edge { int from , to , cost; bool operator<(const Edge &autre){ if(from == autre.from){ return to < autre.to; } return from < autre.from; } }; const int N = 1e5 * 2 + 10; int p[N]; int sz[N]; void make(int a){ p[a] = a; sz[a] = 1; return ; } int find_set(int a){ if(p[a] == a) return a; return p[a] = find_set(p[a]); } bool union_sets(int a , int b){ a = find_set(a); b = find_set(b); if(a == b) return false; if(sz[a] < sz[b]) swap(a,b); p[b] = a; sz[a] += sz[b]; return true; } const int dx[4] = {2 , 0 , 0 , -2} , dy[4] = {0 , 2 , -2 , 0}; int construct_roads(vector<int> x , vector<int> y){ int n = (int)x.size(); if(n == 1){ build({} , {} , {} , {}); return 1; } map<pair<int,int> , int> seen; map<int , pair<int,int>> after; for(int i = 0 ; i < n ; i++){ seen[make_pair(x[i] , y[i])] = i + 1; after[i] = make_pair(x[i] , y[i]); } for(int i = 0 ; i < n ; i++){ make(i); } vector<int> u , q; for(int i = 0 ; i < n ; i++){ for(int j = 0 ; j < 4 ; j++){ int new_x = x[i] + dx[j]; int new_y = y[i] + dy[j]; int m = seen[make_pair(new_x , new_y)]; if(m){ m--; if(union_sets(i , m)){ u.emplace_back(i); q.emplace_back(m); } } } } if(sz[find_set(0)] != n) return 0; map<pair<int,int> , bool> used; vector<int> one , two; for(int i = 0 ; i < (int)u.size() ; i++){ int now_t = u[i] , now_z = q[i]; auto pq = after[now_t] , r = after[now_z]; pair<int,int> choice1 , choice2; if(pq.first == r.first){ choice1 = make_pair(pq.first - 1 , (pq.second+r.second)/2); choice2 = make_pair(pq.first + 1 , (pq.second+r.second)/2); } else{ assert(pq.second == r.second); choice1 = make_pair((pq.first + r.first)/2 , pq.second - 1); choice2 = make_pair((pq.first + r.first) / 2 , pq.second + 1); } if(!used[choice1]){ one.emplace_back(choice1.first); two.emplace_back(choice1.second); used[choice1] = true; } else if(!used[choice2]){ one.emplace_back(choice2.first); two.emplace_back(choice2.second); used[choice2] = true; } } build(u , q , one , two); return 1; } /*int main(){ int n; cin >> n; vector<int> x(n), y(n); for(int i = 0 ; i < n ; i++){ cin >> x[i]; } for(int i = 0 ; i < n ; i++){ cin >> y[i]; } cout << construct_roads(x , y); 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...