oj.uz

답안 #949949

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
949949 2024-03-20T00:52:47 Z koukirocks Love Polygon (BOI18_polygon) C++17
25 / 100
 316 ms 37880 KB 
#include <bits/stdc++.h>
#define speed ios_base::sync_with_stdio(0); cin.tie(0)
#define all(x) (x).begin(),(x).end()
#define F first
#define S second
 
using namespace std;
typedef long long ll;
typedef double db;
typedef long double ldb;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
 
const ll MAX=1e5+10,P=998244353;
const ll INF=0x3f3f3f3f,oo=0x3f3f3f3f3f3f3f3f;
 
int n;
vector<pair<string,string> > eg;
int G[MAX];
vector<int> cptG[MAX];
int dp[MAX][2];

void dfs(int v,int p,vector<bool>& vis,vector<bool>& tmpvis,vector<int>& ccl,int& stt) {
//	cout<<v<<" "<<p<<"\n"<<flush;
	tmpvis[v]=true;
	for (int i:cptG[v]) {
		if (i==p) {
			p=-1;
			continue;
		}
		if (tmpvis[i]) {
			stt=i;
			ccl.push_back(v);
			if (i==v) stt=-1;
			return;
		}
		dfs(i,v,vis,tmpvis,ccl,stt);
		if (stt>=-1) {
//			cout<<v<<" "<<stt<<" stt\n";
			if (stt>=0) {
				ccl.push_back(v);
				if (stt==v) stt=-1;
			}
			return;
		}
	}
	tmpvis[v]=false;
}

int dfsvis(int v,vector<bool>& vis) {
	vis[v]=true;
	int ans=1;
	for (int i:cptG[v]) {
		if (vis[i]) continue;
		ans+=dfsvis(i,vis);
	}
	return ans;
}

void dfs2(int v,int p,vector<bool>& isccl) {
	if (cptG[v].size()==1) {
		dp[v][0]=0;
		dp[v][1]=-INF;
		return;
	}
	dp[v][0]=0;
	for (int i:cptG[v]) {
		if (i==p) continue;
		if (isccl[i]) continue;
		dfs2(i,v,isccl);
		dp[v][0]+=max(dp[i][0],dp[i][1]);
	}
	dp[v][1]=0;
	for (int i:cptG[v]) {
		if (i==p) continue;
		if (isccl[i]) continue;
		dp[v][1]=max(dp[v][1],dp[v][0]-max(dp[i][0],dp[i][1])+dp[i][0]+1);
	}
}
 
int main() {
	speed;
	cin>>n;
	vector<string> dct;
	for (int i=0;i<n;i++) {
		string a,b;
		cin>>a>>b;
		eg.emplace_back(a,b);
		dct.push_back(a);
		dct.push_back(b);
	}
	sort(all(dct));
	dct.resize(unique(all(dct))-dct.begin());
//	for (string s:dct) cout<<s<<"\n";
//	cout<<"name\n";
	fill(G,G+n,n);
	for (int i=0;i<n;i++) {
		auto [a,b]=eg[i];
		int va=lower_bound(all(dct),a)-dct.begin();
		int vb=lower_bound(all(dct),b)-dct.begin();
		G[va]=vb;
//		cout<<va<<" "<<vb<<" vab\n";
//		cout<<va<<" "<<G[G[va]]<<" G\n";
		cptG[va].push_back(vb);
		if (va!=vb) cptG[vb].push_back(va);
	}
//	for (int i=0;i<n;i++) {
//		cout<<i<<" : ";
//		for (int j:cptG[i]) cout<<j<<" ";
//		cout<<"\n";
//	}
	if (n&1) {
		cout<<"-1\n";
		return 0;
	}
	vector<bool> vis(n,0),tmpvis(n,0);
	vector<bool> isccl(n,0);
	int ttl=0;
	for (int i=0;i<n;i++) {
		if (vis[i]) continue;
		vector<int> ccl;
		int stt=-2;
		dfs(i,-1,vis,tmpvis,ccl,stt);
		int sz=dfsvis(i,vis);
		if (sz<=2) {
			if (sz==2) ttl+=2;
			continue;
		}
//		cout<<i<<" i\n"<<flush;
//		for (int j:ccl) cout<<j<<" ";
//		cout<<" ccl\n"<<flush;
		for (int j:ccl) isccl[j]=true;
		for (int j:ccl) {
//			cout<<j<<" rt\n"<<flush;
			dfs2(j,-1,isccl);
		}
		vector<vector<int> > cdp(ccl.size(),vector<int>(2,0));
		cdp[0][0]=dp[ccl[0]][0];
		cdp[0][1]=dp[ccl[0]][1];
		for (i=1;i<ccl.size();i++) {
			cdp[i][0]=max(cdp[i-1][0],cdp[i-1][1])+dp[ccl[i]][0];
			cdp[i][1]=max(max(cdp[i-1][0],cdp[i-1][1])+dp[ccl[i]][1],cdp[i-1][0]+dp[ccl[i]][0]+1);
		}
		int ans=max(cdp[ccl.size()-1][0],cdp[ccl.size()-1][1]);
		int tmp=ccl[0];
		for (int j=0;j<ccl.size()-1;j++) ccl[j]=ccl[j+1];
		ccl[ccl.size()-1]=tmp;
//		for (int j:ccl) cout<<j<<" ";
//		cout<<" ccl\n"<<flush;
		fill(all(cdp),vector<int>(2,0));
		cdp[0][0]=dp[ccl[0]][0];
		cdp[0][1]=dp[ccl[0]][1];
		for (i=1;i<ccl.size();i++) {
			cdp[i][0]=max(cdp[i-1][0],cdp[i-1][1])+dp[ccl[i]][0];
			cdp[i][1]=max(max(cdp[i-1][0],cdp[i-1][1])+dp[ccl[i]][1],cdp[i-1][0]+dp[ccl[i]][0]+1);
		}
		ans=max(ans,max(cdp[ccl.size()-1][0],cdp[ccl.size()-1][1]));
		ttl+=ans;
	}
	cout<<n-ttl<<"\n";
	return 0;
}

/*
4
a f
d f
g f
f f
*/

Compilation message

polygon.cpp: In function 'int main()':
polygon.cpp:140:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  140 |   for (i=1;i<ccl.size();i++) {
      |            ~^~~~~~~~~~~
polygon.cpp:146:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  146 |   for (int j=0;j<ccl.size()-1;j++) ccl[j]=ccl[j+1];
      |                ~^~~~~~~~~~~~~
polygon.cpp:153:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  153 |   for (i=1;i<ccl.size();i++) {
      |            ~^~~~~~~~~~~

Subtask #1
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 3416 KB Output is correct
2 Correct 1 ms 3420 KB Output is correct
3 Correct 1 ms 3420 KB Output is correct
4 Correct 1 ms 3420 KB Output is correct
5 Correct 2 ms 3420 KB Output is correct
6 Correct 1 ms 3420 KB Output is correct
7 Correct 1 ms 3420 KB Output is correct
8 Incorrect 1 ms 3420 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 3420 KB Output is correct
2 Correct 1 ms 3420 KB Output is correct
3 Correct 1 ms 3420 KB Output is correct
4 Correct 179 ms 35944 KB Output is correct
5 Correct 316 ms 24488 KB Output is correct
6 Correct 166 ms 37880 KB Output is correct
7 Correct 127 ms 24212 KB Output is correct

Subtask #3
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 132 ms 20792 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 3416 KB Output is correct
2 Correct 1 ms 3420 KB Output is correct
3 Correct 1 ms 3420 KB Output is correct
4 Correct 1 ms 3420 KB Output is correct
5 Correct 2 ms 3420 KB Output is correct
6 Correct 1 ms 3420 KB Output is correct
7 Correct 1 ms 3420 KB Output is correct
8 Incorrect 1 ms 3420 KB Output isn't correct
9 Halted 0 ms 0 KB -