oj.uz

Submission #1108537

# Submission time Handle Problem Language Result Execution time Memory
1108537 2024-11-04T11:21:30 Z _rain_ Love Polygon (BOI18_polygon) C++14
54 / 100
 132 ms 35080 KB 
#include<bits/stdc++.h>
using namespace std;
 
typedef long long ll;
#define name "main"
 
const int N=(int)1e5;
vector<string>nen;
string s1[N+2],s2[N+2];
int deg[N+2],num[N+2],low[N+2],id[N+2],scc=0,timedfs=0;
int u[N+2],v[N+2],to[N+2],dp[N+2][2],n;
vector<int>ord,bag[N+2],ke[N+2];
bool used[N+2],del[N+2];
 
void buildup(int u){
	num[u]=low[u]=++timedfs;
	ord.push_back(u);
	
	if (!num[to[u]]&&!del[to[u]]){
		buildup(to[u]);
		low[u]=min(low[u],low[to[u]]);
	}
	else if (!del[to[u]]) low[u]=min(low[u],num[to[u]]);
	if (low[u]==num[u]){
		int v;
		++scc;
		do{
			v=ord.back();
			ord.pop_back();
			id[v]=scc;
			del[v]=true;
			bag[id[v]].push_back(v);
		}while(v!=u);
	}
}
void dfs(int u){
	if (ke[u].size()==0){
		dp[u][0]=0;
		dp[u][1]=1;
		return;
	}
	for(auto&v:ke[u]){
		dfs(v);
		dp[u][1]+=dp[v][0];
	}
	dp[u][1]++;
	for(auto&v:ke[u]){
		dp[u][0]=max(dp[u][0],dp[u][1]-1+max(0,dp[v][1]-dp[v][0]));
	}
}
 
int32_t main(){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	cin>>n;
	if (n%2==1){
		cout<<-1;
		exit(0);
	}
	for(int i=1;i<=n;++i){
		cin>>s1[i]>>s2[i];
		nen.push_back(s1[i]);
		nen.push_back(s2[i]);
	}
	sort(nen.begin(),nen.end());
	nen.resize(unique(nen.begin(),nen.end())-nen.begin());
	for(int i=1;i<=n;++i){
		u[i]=upper_bound(nen.begin(),nen.end(),s1[i])-nen.begin();
		v[i]=upper_bound(nen.begin(),nen.end(),s2[i])-nen.begin();
		to[u[i]]=v[i];
	}
	assert(nen.size()==n);
	for(int i=1;i<=n;++i) if (!num[i]) buildup(i);
	for(int i=1;i<=scc;++i){
		for(auto&u:bag[i]){
			if (id[to[u]]!=i){
				ke[id[to[u]]].push_back(i);
				deg[i]++;
			}
		}
	}
	for(int i=1;i<=scc;++i) {
		sort(ke[i].begin(),ke[i].end());
		ke[i].resize(unique(ke[i].begin(),ke[i].end())-ke[i].begin());
	}
	int ans=0;
	// for(int i=1;i<=n;++i){
	// 	cout<<u[i]<<' '<<v[i]<<'\n';
	// }
	// for(int i=1;i<=n;++i) cout<<id[i]<<' '; cout<<'\n';
	for(int i=1;i<=scc;++i){
		if (deg[i]==0){
			dfs(i);
			if (bag[i].size()==2) ans+=2; else ans+=bag[i].size()/2;
			if (bag[i].size()%2==0) ans+=max(dp[i][0],dp[i][1]-1); else ans+=dp[i][0];
		}
	}
	cout<<n-ans;
	exit(0);
}

Compilation message

In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from polygon.cpp:1:
polygon.cpp: In function 'int32_t main()':
polygon.cpp:73:19: warning: comparison of integer expressions of different signedness: 'std::vector<std::__cxx11::basic_string<char> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   73 |  assert(nen.size()==n);
      |         ~~~~~~~~~~^~~

Subtask #1
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14928 KB Output is correct
2 Correct 3 ms 14928 KB Output is correct
3 Correct 3 ms 14928 KB Output is correct
4 Correct 2 ms 14928 KB Output is correct
5 Correct 3 ms 12880 KB Output is correct
6 Correct 3 ms 12880 KB Output is correct
7 Correct 3 ms 14940 KB Output is correct
8 Incorrect 3 ms 14928 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14928 KB Output is correct
2 Correct 3 ms 14928 KB Output is correct
3 Correct 3 ms 14928 KB Output is correct
4 Correct 110 ms 31236 KB Output is correct
5 Correct 107 ms 23984 KB Output is correct
6 Correct 115 ms 32260 KB Output is correct
7 Correct 3 ms 13056 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 28668 KB Output is correct
2 Correct 122 ms 30384 KB Output is correct
3 Correct 92 ms 26356 KB Output is correct
4 Correct 3 ms 12880 KB Output is correct
5 Correct 132 ms 35080 KB Output is correct
6 Correct 117 ms 27824 KB Output is correct
7 Correct 126 ms 27840 KB Output is correct
8 Correct 115 ms 27408 KB Output is correct
9 Correct 108 ms 27312 KB Output is correct
10 Correct 92 ms 27144 KB Output is correct
11 Correct 4 ms 14928 KB Output is correct
12 Correct 3 ms 14928 KB Output is correct
13 Correct 3 ms 14928 KB Output is correct
14 Correct 2 ms 14928 KB Output is correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14928 KB Output is correct
2 Correct 3 ms 14928 KB Output is correct
3 Correct 3 ms 14928 KB Output is correct
4 Correct 2 ms 14928 KB Output is correct
5 Correct 3 ms 12880 KB Output is correct
6 Correct 3 ms 12880 KB Output is correct
7 Correct 3 ms 14940 KB Output is correct
8 Incorrect 3 ms 14928 KB Output isn't correct
9 Halted 0 ms 0 KB -