Submission #268668

#	Time	Username	Problem	Language	Result	Execution time	Memory
268668		thomas_li	Love Polygon (BOI18_polygon)	C++17	100 / 100	292 ms	17148 KiB

polygon

#pragma GCC optimize "Ofast"
#pragma GCC optimize "unroll-loops"
#pragma GCC optimize "omit-frame-pointer"
#pragma GCC optimize "prefetch-loop-arrays"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/priority_queue.hpp>
using namespace std;
using ll = long long;
using ld = long double;
using vi = vector<int>;
using pi = pair<int, int>;
using pll = pair<ll, ll>;
constexpr int INF = 0x3f3f3f3f; constexpr ll LLINF = 0x3f3f3f3f3f3f3f3f;
#ifdef __MINGW32__ /* CF */
inline int getchar_unlocked() { return _getchar_nolock(); }
inline int putchar_unlocked(int c) { return _putchar_nolock(c); }
#endif
#define gc getchar_unlocked()
#define pc(x) putchar_unlocked(x)
template<typename T> void scan(T &x){x = 0;bool _=0; T c=gc;_=c==45;c=_?gc:c;while(c<48||c>57)c=gc;for(;c<48||c>57;c=gc);for(;c>47&&c<58;c=gc)x=(x<<3)+(x<<1)+(c&15);x=_?-x:x;}
template<typename T> void printn(T n){bool _=0;_=n<0;n=_?-n:n;char snum[65];int i=0;do{snum[i++]=n%10+48;n/= 10;}while(n);--i;if (_)pc(45);while(i>=0)pc(snum[i--]);}
template<typename First, typename ... Ints> void scan(First &arg, Ints&... rest){scan(arg);scan(rest...);}
template<typename T> void print(T n){printn(n);pc(10);}
template<typename First, typename ... Ints> void print(First arg, Ints... rest){printn(arg);pc(32);print(rest...);}
#define db(x)       { cerr << #x << " = " << x << endl; }
template <typename T> void _dbarr(T* a, size_t sz){ for(int i = 0; i < sz; i++) cerr << a[i] << " \n"[i == sz-1]; }
template <typename T> void _dbarr(vector<T> a, size_t sz){ for(int i = 0; i < sz; i++) cerr << a[i] << " \n"[i == sz-1]; }
#define dbarr(x, n) {cerr << #x << ": "; _dbarr((x),(n));}
#define all(x) begin(x), end(x)
#define pb push_back
#define eb emplace_back
//#define mp make_pair
#define fs first
#define sn second

const int MM = 1e5+5;
int n,ind[MM],nxt[MM];
bool done[MM];
vector<int> adj[MM];
string back[MM];
map<string,int> mp;

int mx = 0;
int conv(string s)
{
	if(mp.find(s) ==mp.end()) mp.insert({s,mp.size()}), back[mp.size()-1] = s; // 0-index
	return mp[s];
}

int main() 
{
	cin.tie(0)->sync_with_stdio(0);
	cin >> n;
	if(n & 1) return 0*printf("-1\n"); 
	// even n is always possible
	
	for(int i = 0; i < n; i++)
	{
		string a,b;
		cin >> a >> b;
		int aa = conv(a), bb = conv(b);
		nxt[aa] = bb;
		ind[bb]++;
	}
	
	//for(auto&[k,v]:mp) cout << k << " " << v << "\n";
	
	
	for(int i = 0; i < n; i++) if(nxt[nxt[i]] == i && nxt[i] != i) done[i] = 1, done[nxt[i]] = 1;
	queue<int> q;
	for(int i = 0; i < n; i++) if(!done[i] && ind[i] == 0) q.push(i);
	
	int ans = 0;
	while(!q.empty())
	{
		int u = q.front(); q.pop();
		//db(back[u])
		ans++; done[u] = 1;
		if(!done[nxt[u]])
		{			
			if(--ind[nxt[nxt[u]]] == 0 && !done[nxt[nxt[u]]]) q.push(nxt[nxt[u]]);
			//db(back[nxt[u]])
			done[nxt[u]] = 1;
		}
	}
	//db(done[conv("d")])
	for(int i = 0; i < n; i++)
	{
		if(!done[i])
		{
			int len = 1;
			done[i] = 1;
			for(int pos = nxt[i]; pos != i; done[pos] = 1, pos = nxt[pos]) len++;
			//db(len)
			ans += (len+1)/2;
		}
	}

	cout << ans << "\n";
}

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