oj.uz

Submission #793021

# Submission time Handle Problem Language Result Execution time Memory
793021 2023-07-25T12:35:45 Z UmairAhmadMirza Love Polygon (BOI18_polygon) C++14
29 / 100
 427 ms 29864 KB 
#include <bits/stdc++.h>
using namespace std;
int const N=1e5+5;
map<string,int> mp;
int suc[N];
vector<int> lover[N];
vector<int> adj[N];
vector<int> cc[N];
int c=0;
int ccn[N];
int _dp[N],dp[N];
void dfs(int node){
	ccn[node]=c;
	cc[c].push_back(node);
	for(auto i:adj[node])
		if(ccn[i]==0)
			dfs(i);
}
void LIS(int root){//largest_independent_set
	// cout<<root<<endl;
	for(auto i:lover[root])
		if(i!=root)
			LIS(i);
	_dp[root]=1;
	int maxx=0;
	for(auto i:lover[root])
		if(i!=root){
			_dp[root]+=dp[i];
			dp[root]+=dp[i];
			maxx=max(maxx,_dp[i]-dp[i]);
		}
	dp[root]+=maxx;
}
int main(){
	int n;
	cin>>n;
	string a,b;
	int sz=1;
	for (int i = 0; i < n; ++i)
	{
		cin>>a>>b;
		if(mp[a]==0){
			mp[a]=sz;
			sz++;
		}
		if(mp[b]==0){
			mp[b]=sz;
			sz++;
		}
		// cout<<mp[a]<<' '<<mp[b]<<endl;
		suc[mp[a]]=mp[b];
		if(mp[a]==mp[b])
			continue;
		adj[mp[b]].push_back(mp[a]);
		adj[mp[a]].push_back(mp[b]);
		suc[mp[a]]=mp[b];
		lover[mp[b]].push_back(mp[a]);
	}
	if(n%2){
		cout<<-1<<endl;
		return 0;
	}
	for (int i = 1; i <=n; ++i)
		if(ccn[i]==0){
			c++;
			dfs(i);
		}
	int ans=0;
	for (int i = 1; i <=c; ++i)
	{
		for(auto v:cc[i])
			if(suc[v]==v){
				LIS(v);
				ans+=dp[v];
			}
	}
	cout<<n-ans<<endl;
	// for (int i = 1; i <=n; ++i)
	// {
	// 	cout<<dp[i]<<' '<<_dp[i]<<endl;
	// }
	return 0;
}

Subtask #1
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7360 KB Output is correct
2 Correct 3 ms 7380 KB Output is correct
3 Correct 3 ms 7252 KB Output is correct
4 Incorrect 3 ms 7252 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7364 KB Output is correct
2 Incorrect 4 ms 7296 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 402 ms 24888 KB Output is correct
2 Correct 410 ms 26272 KB Output is correct
3 Correct 204 ms 21936 KB Output is correct
4 Correct 411 ms 22488 KB Output is correct
5 Correct 427 ms 29864 KB Output is correct
6 Correct 423 ms 24220 KB Output is correct
7 Correct 406 ms 24252 KB Output is correct
8 Correct 313 ms 23980 KB Output is correct
9 Correct 389 ms 23888 KB Output is correct
10 Correct 269 ms 23240 KB Output is correct
11 Correct 3 ms 7380 KB Output is correct
12 Correct 4 ms 7364 KB Output is correct
13 Correct 5 ms 7360 KB Output is correct
14 Correct 3 ms 7380 KB Output is correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7360 KB Output is correct
2 Correct 3 ms 7380 KB Output is correct
3 Correct 3 ms 7252 KB Output is correct
4 Incorrect 3 ms 7252 KB Output isn't correct
5 Halted 0 ms 0 KB -