제출 #1038177

#제출 시각아이디문제언어결과실행 시간메모리
1038177codexistentLove Polygon (BOI18_polygon)C++14
50 / 100
2040 ms40628 KiB
#include <bits/stdc++.h> using namespace std; #define MAXN 100005 #define FOR(i, a, b) for(int i = a; i <= b; i++) #define f first #define s second int n, ec[MAXN]; string st[MAXN], nx[MAXN]; map<string, int> idx; set<int> adj[MAXN]; set<pair<int, int>> e; bool d[MAXN]; int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); cin >> n; FOR(i, 1, n) ec[i] = 0; FOR(i, 1, n){ cin >> st[i]; idx.insert({st[i], i}); cin >> nx[i]; } if(n % 2) { cout << -1 << endl; return 0; } int r = 0; FOR(i, 1, n){ d[i] = (idx[nx[idx[nx[i]]]] == i && idx[nx[i]] != i); } FOR(i, 1, n){ if(i == idx[nx[i]] || d[i] || d[idx[nx[i]]]) continue; e.insert({i, idx[nx[i]]}); ec[i]++, ec[idx[nx[i]]]++; } FOR(i, 1, n){ if(i == idx[nx[i]] || d[i] || d[idx[nx[i]]]) continue; adj[i].insert(idx[nx[i]]); //cout << "DCVVB: " << idx[nx[i]] << endl; adj[idx[nx[i]]].insert(i); } set<pair<int, int>> se; FOR(i, 1, n) if(!d[i]) se.insert({ec[i], i}); while(se.size()){ auto si = *se.begin(); if(si.f == 0){ r++; //cout << st[si.s] << " FALLALEUJAH! " << endl; }else{ int j = 0, jmn = INT_MAX; for(int i : adj[si.s]){ if(jmn > ec[i]) j = i, jmn = ec[i]; } r++; //cout << st[si.s] << " ~ " << st[j] << " : " << si.s << " " << j << endl; se.erase({jmn, j}); for(int j2 : adj[j]){ se.erase({ec[j2], j2}); adj[j2].erase(j), ec[j2]--; se.insert({ec[j2], j2}); } } for(int i2 : adj[si.s]) { se.erase({ec[i2], i2}); adj[i2].erase(si.s), ec[i2]--; se.insert({ec[i2], i2}); } se.erase(se.begin()); } cout << r << "\n"; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...