제출 #1032895

#제출 시각아이디문제언어결과실행 시간메모리
1032895anangoLove Polygon (BOI18_polygon)C++17
100 / 100
587 ms39984 KiB
#include <bits/stdc++.h> #define int long long using namespace std; int INF = 1LL<<30; vector<vector<int>> adjlist,revadjlist; //revadjlist = original adjlist, adjlist is the reversed version vector<int> dp0; vector<int> dp1; //dp0 = maximum set of unmoved vertices choosable if this vertex is taken, dp1 if it's not taken signed main() { /*#ifndef ONLINE_JUDGE // for getting input from input.txt freopen("input.txt", "r", stdin); // for writing output to output.txt freopen("output.txt", "w", stdout); #endif*/ /*#ifdef ONLINE_JUDGE ios_base::sync_with_stdio(false); cin.tie(NULL); #endif*/ //fast IO int n; cin >> n; adjlist=vector<vector<int>>(n); revadjlist=vector<vector<int>>(n); dp0=vector<int>(n,0); dp1=vector<int>(n,0); map<string,int> names; int ct=0; vector<int> sources; vector<int> child(n); vector<set<int>> parents(n); for (int i=0; i<n; i++) { string s,t; cin >> s >> t; if (!names.count(s)) { names[s] = ct; ct++; } if (!names.count(t)) { names[t] = ct; ct++; } revadjlist[names[s]].push_back(names[t]); child[names[s]]=names[t]; parents[names[t]].insert(names[s]); if (s==t) { sources.push_back(names[s]); continue; } adjlist[names[s]].push_back(names[t]); adjlist[names[t]].push_back(names[s]); } if (n%2==1) { cout << -1 << endl; return 0; } int ops=0; set<int> active; for (int i=0; i<n; i++) active.insert(i); for (int i=0; i<n; i++) { if (active.count(i) && active.count(child[i]) && i!=child[i] && i==child[child[i]]) { //cout << "easy remove" << " " << i <<" " << child[i] << endl; active.erase(i); active.erase(child[i]); } } vector<int> vals; for (int i=0; i<n; i++) { if (parents[i].size()==0) { vals.push_back(i); } } while (active.size()) { if (!vals.size()) vals.push_back(*active.begin()); //do a BFS, if it's the last parent of a child, add the child int rem = vals.back(); vals.pop_back(); ops++; active.erase(rem); parents[child[rem]].erase(rem); //cout << "removing " << rem <<" " << child[rem] << endl; if (active.count(child[rem])) { active.erase(child[rem]); parents[child[child[rem]]].erase(child[rem]); if (active.count(child[child[rem]]) && parents[child[child[rem]]].size()==0) { vals.push_back(child[child[rem]]); } } } cout << ops << endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...