oj.uz

답안 #530378

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
530378 2022-02-25T09:06:25 Z fatemetmhr Love Polygon (BOI18_polygon) C++17
29 / 100
 292 ms 27812 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;


#define pb    push_back
#define fi    first
#define se    second

const int maxn5 = 3e5 + 10;

int a[maxn5], req[maxn5];

int dp[2][maxn5]; // dp[0 -> khodesh nabashad/ 1 -> bashad][v]
int pd[maxn5], num[maxn5];
int sz[maxn5], parof[maxn5];
map <string, int> av;
bool mark[maxn5], incy[maxn5];
vector <int> adj[maxn5], ver, tmp;
int nn = 0, cmp[maxn5];

inline int dfs2(int v){
	//cout << "hello " << v << endl;
	mark[v] = true;
	int cy = -1;
	int u = parof[v];
	cmp[v] = nn;
	//cout << "ok " << v << ' ' << u << endl;
	if(!mark[u]){
		int z = dfs2(u);
		//cout << "aha " << z << endl;
		if(cy == -1)
			cy = z;
	}
	else if(cmp[u] == cmp[v]){
		cy = u;
	}
	//cout << ' ' << v << ' ' << cy << endl;
	if(cy != -1)
		incy[v] = true;
	return (cy == v ? -1 : cy);
}

inline void dfs(int v){
	//cout << "hello " << v << endl;
	dp[0][v] = 0;
	sz[v] = 1;
	bool re = false;
	for(auto u : adj[v]) if(!incy[u]){
		dfs(u);
		sz[v] += sz[u];
		dp[0][v] += dp[1][u] + (sz[u] % 2);
		re = true;
	}
	if(!re){
		dp[1][v] = 0;
		return;
	}
	dp[1][v] = maxn5;
	for(auto u : adj[v]) if(!incy[u]){
		int val = dp[0][v] - dp[1][u] - (sz[u] % 2);
		val += dp[0][u] + (sz[u] % 2 == 0);
		val++;
		if(sz[v] % 2 == 1)
			val--;
		dp[1][v] = min(dp[1][v], val);
	}
	if(sz[v] % 2 == 0){
		dp[0][v]--;
	}
	else{
		dp[1][v] = min(dp[1][v], dp[0][v]);
	}
	//cout << v << ' ' << dp[0][v] << ' ' << dp[1][v] << endl;
	return;
}

inline int find_next(int v){
	return parof[v];
}

int main(){
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	
	int n; cin >> n;
	int ind = 0;
	for(int i = 0; i < n; i++){
		string s, t; cin >> s >> t;
		if(av.find(s) == av.end())
			av[s] = ind++;
		if(av.find(t) == av.end())
			av[t] = ind++;
		adj[av[t]].pb(av[s]);
		parof[av[s]] = av[t];
	}
	/*
	for(auto it = av.begin(); it != av.end(); it++)
		cout << (it -> fi) << ' ' << (it -> se) << endl;
	//*/
	if(n % 2 == 1)
		return cout << -1 << endl, 0;
	memset(mark, false, sizeof mark);
	for(int i = 0; i < n; i++) if(!mark[i]){
		dfs2(i);
		nn++;
	}
	for(int i = 0; i < n; i++) if(incy[i]){
		dfs(i);
	}
	memset(mark, false, sizeof mark);
	ll ans = 0;
	for(int i = 0; i < n; i++) if(incy[i] && !mark[i]){
		//cout << "oh a new day! " << i << endl;
		ver.clear();
		int v = find_next(i);
		mark[i] = true;
		ver.pb(i);
		while(v != i){
			mark[v] = true;
			ver.pb(v);
			v = find_next(v);
			//cout << v << ' ' << i << endl;
		}
		if(ver.size() == 1){
			ans += dp[1][i];
			if(sz[i] % 2 == 1)
				ans++;
			continue;
		}
		pd[0] = dp[1][i];
		num[0] = sz[i];
		for(int j = 1; j < ver.size(); j++){
			int u = ver[j];
			num[j] = num[j - 1] + sz[u];
			pd[j] = pd[j - 1] + dp[1][u] + 2 * (num[j - 1] % 2 == 1 && sz[u] % 2 == 1);
			int val = (j == 1 ? 0 : pd[j - 2]) + dp[0][u] + dp[0][ver[j - 1]] + 1;
			int f = (sz[u] % 2 == 0) + (sz[ver[j - 1]] % 2 == 0) + (j > 1 && num[j - 2] % 2 == 1);
			if(f >= 2)
				val += 2;
			pd[j] = min(pd[j], val);
			val = pd[j - 1] + dp[0][u] + 2 * (num[j - 1] % 2 == 1 && sz[u] % 2 == 0);
			pd[j] = min(pd[j], val);
		}
		int cur = pd[ver.size() - 1] + (num[ver.size() - 1] % 2);
		tmp.clear();
		tmp.pb(ver.back());
		for(auto u : ver)
			tmp.pb(u);
		tmp.pop_back();
		ver.clear();
		for(auto u : tmp)
			ver.pb(u);
		pd[0] = dp[1][i];
		num[0] = sz[i];
		for(int j = 1; j < ver.size(); j++){
			int u = ver[j];
			num[j] = num[j - 1] + sz[u];
			pd[j] = pd[j - 1] + dp[1][u] + 2 * (num[j - 1] % 2 == 1 && sz[u] % 2 == 1);
			int val = (j == 1 ? 0 : pd[j - 2]) + dp[0][u] + dp[0][ver[j - 1]] + 1;
			int f = (sz[u] % 2 == 0) + (sz[ver[j - 1]] % 2 == 0) + (j > 1 && num[j - 2] % 2 == 1);
			if(f >= 2)
				val += 2;
			pd[j] = min(pd[j], val);
			val = pd[j - 1] + dp[0][u] + 2 * (num[j - 1] % 2 == 1 && sz[u] % 2 == 0);
			pd[j] = min(pd[j], val);
		}
		cur = min(cur, pd[ver.size() - 1] + (num[ver.size() - 1] % 2));
		if(ver.size() == 2){
			cur = min(cur, dp[0][ver[0]] + dp[0][ver[1]] + 2 * (sz[ver[0]] % 2 == 0 && sz[ver[1]] % 2 == 0));
		}
		ans += cur;
	}

	cout << ans << endl;
}

Compilation message

polygon.cpp: In function 'int main()':
polygon.cpp:134:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  134 |   for(int j = 1; j < ver.size(); j++){
      |                  ~~^~~~~~~~~~~~
polygon.cpp:157:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  157 |   for(int j = 1; j < ver.size(); j++){
      |                  ~~^~~~~~~~~~~~

Subtask #1
0 / 21.0

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

Subtask #2
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 7628 KB Output is correct
2 Correct 4 ms 7628 KB Output is correct
3 Incorrect 4 ms 7628 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 254 ms 19876 KB Output is correct
2 Correct 292 ms 21844 KB Output is correct
3 Correct 195 ms 20576 KB Output is correct
4 Correct 222 ms 17120 KB Output is correct
5 Correct 264 ms 27812 KB Output is correct
6 Correct 252 ms 19012 KB Output is correct
7 Correct 234 ms 19052 KB Output is correct
8 Correct 254 ms 19488 KB Output is correct
9 Correct 217 ms 18540 KB Output is correct
10 Correct 174 ms 17788 KB Output is correct
11 Correct 6 ms 7628 KB Output is correct
12 Correct 6 ms 7628 KB Output is correct
13 Correct 4 ms 7628 KB Output is correct
14 Correct 4 ms 7628 KB Output is correct

Subtask #4
0 / 25.0

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