Submission #797929

#TimeUsernameProblemLanguageResultExecution timeMemory
797929senthetaLove Polygon (BOI18_polygon)C++17
0 / 100
237 ms25724 KiB
// author : sentheta aka vanwij #ifdef VANWIJ #include"/home/user/code/bits/stdc++.h" #define DBG 1 #else #include"bits/stdc++.h" #define DBG 0 #endif using namespace std; #define Int long long #define V vector #define pii pair<int,int> #define ff first #define ss second static mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); #define pow2(x) (1LL<<(x)) #define msb(x) (63-__builtin_clzll(x)) #define bitcnt(x) (__builtin_popcountll(x)) #define nl '\n' #define _ << ' ' << #define all(x) (x).begin(), (x).end() #define rep(i,a,b) for(int i = (int)(a); i < (int)(b); i++) #define cerr if(DBG) cout #define dbg(x) {cerr << "?" << #x << " : " << (x) << endl << flush;} #define int long long // const Int MOD = 1e9+7; const Int MOD = 998244353; Int bpow(Int a,Int b){ Int ret = 1; for(;b; a=a*a%MOD,b/=2) if(b&1) ret = ret*a%MOD; return ret; } Int inv(Int a){return bpow(a,MOD-2);} void solve(); int TC, ALLTC; signed main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cout << fixed << setprecision(7); // cin >> ALLTC; for(TC=1; TC<=ALLTC; TC++) solve(); return 0; solve(); } const int N = 1e5+5; int n; int out[N]; set<int> in[N]; bool flag[N]; int namecnt = 0; string names[N]; map<string,int> mp; void solve(){ cin >> n; if(n%2){ cout << -1 << nl; return; } rep(i,0,n){ string a, b; cin >> a >> b; if(!mp.count(a)){ mp[a] = namecnt; names[namecnt++] = a; } if(!mp.count(b)){ mp[b] = namecnt; names[namecnt++] = b; } int u = mp[a], v = mp[b]; out[u] = v; in[v].insert(u); cerr << u _ v << nl; } // {-indeg, x} priority_queue<pii> pq; rep(x,0,n){ if(out[x]!=x && out[out[x]]==x){ flag[x] = 1; } else{ pq.push({-in[x].size(), x}); } } int ans = 0, fre = 0; while(!pq.empty()){ auto[deg,x] = pq.top(); pq.pop(); deg *= -1; if(deg!=(int)in[x].size() || flag[x]) continue; dbg(x); if(out[x]!=x && !flag[out[x]]){ flag[x] = flag[out[x]] = 1; out[out[x]] = x; in[out[x]].erase(x); ans++; } else{ bool found = 0; for(int y : in[x]){ if(y!=x && !found && !flag[y]){ flag[x] = flag[y] = 1; out[x] = y; found = 1; ans++; break; } } if(!found){ fre++; } } dbg(out[x]); dbg(out[out[x]]); } ans += fre; cout << ans << nl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...