제출 #797933

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
797933		sentheta	Love Polygon (BOI18_polygon)	C++17	100 / 100	252 ms	25964 KiB

polygon

// 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;
			
			in[out[out[x]]].erase(out[x]);
			pq.push({-in[out[out[x]]].size(), out[out[x]]});
			
			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;
				}
			}
			assert(!found);
			if(!found){
				fre++;
			}
		}
		
		dbg(out[x]);
		dbg(out[out[x]]);
	}
	ans += fre;
	
	cout << ans << nl;
	
	
	
	
	
	
}

• Subtask 1: 21 / 21
• Subtask 2: 25 / 25
• Subtask 3: 29 / 29
• Subtask 4: 25 / 25