oj.uz

Submission #1098738

# Submission time Handle Problem Language Result Execution time Memory
1098738 2024-10-09T19:50:01 Z vjudge1 Love Polygon (BOI18_polygon) C++17
46 / 100
 2000 ms 15916 KB 
#include <bits/stdc++.h>

using namespace std;

#define ar array
#define int long long
#define ld long double
#define crash assert(69 == 420)

const int N = 2e5 + 20;
const int MOD = 1e9 + 7;
const int INF = 1e18;
const int X = 100;

int p[N];
int n;

namespace sub1{
	vector<int> g[N];
	bitset<N> vis;
	int cnt = 0;

	void dfs(int x){
		vis[x] = 1;
		cnt++;
		for(auto u: g[x]){
			if(!vis[u])dfs(u);
		}
	}

	bool check(int msk){
		vector<int> v;
		for(int i = 0;i < n;i++){
			if(p[i] == i){
				if((1 << i) & msk){

				}else return 0;
			}
		}
		for(int i = 0;i < n;i++)g[i].clear();
		vis &= 0;
		for(int i = 0;i < n;i++){
			if((1 << i) & msk){

			}else{
				g[i].push_back(p[i]);
				g[p[i]].push_back(i);
			}
		}
		for(int i = 0;i<n;i++){
			if(!vis[i]){
				cnt = 0;
				dfs(i);
				if(cnt > 2)return 0;
			}
		}
		return 1;
	}
};

namespace sub2{
	void solve(){
		int ans = 0;
		bitset<N> vis;
		for(int i = 0;i < n;i++){
			if(vis[i])continue;
			int u = p[i];
			vis[i] = 1;
			int cnt = 1;
			while(u != i){
				vis[u] = 1;
				cnt++;
				u = p[u];
			}
			if(cnt % 2)ans += cnt / 2 + 1;
			else if(cnt > 2)ans += cnt / 2;
		}
		cout<<ans;
	}

};

signed main(){ios_base::sync_with_stdio(false);cin.tie(0);
	//int n;
	cin>>n;
	if(n % 2){
		cout<<-1<<endl;
		return 0;
	}
	map<string, int> mp;
	int G = 0;
	for(int  i = 0;i < n;i++){
		string a, b;
		cin>>a>>b;
		if(!mp.count(a))mp[a] = G++;
		if(!mp.count(b))mp[b] = G++;
		p[mp[a]] = mp[b];
	}
	if(n <= 20){
		int ans = INF;
		for(int i = 0;i < (1 << n);i++){
			if(sub1::check(i))ans = min(ans, (int)__builtin_popcount(i));
		}
		cout<<ans;
		return 0;
	}
	sub2::solve();
}

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 240 ms 4952 KB Output is correct
2 Correct 255 ms 4956 KB Output is correct
3 Correct 244 ms 5160 KB Output is correct
4 Correct 2 ms 4956 KB Output is correct
5 Correct 2 ms 4956 KB Output is correct
6 Correct 2 ms 4956 KB Output is correct
7 Correct 239 ms 5160 KB Output is correct
8 Correct 476 ms 4956 KB Output is correct
9 Correct 121 ms 5156 KB Output is correct
10 Correct 448 ms 4952 KB Output is correct
11 Correct 236 ms 4956 KB Output is correct
12 Correct 2 ms 4952 KB Output is correct
13 Correct 2 ms 4956 KB Output is correct
14 Correct 3 ms 4952 KB Output is correct
15 Correct 2 ms 4956 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4956 KB Output is correct
2 Correct 2 ms 4956 KB Output is correct
3 Correct 2 ms 4956 KB Output is correct
4 Correct 129 ms 13648 KB Output is correct
5 Correct 153 ms 15696 KB Output is correct
6 Correct 129 ms 15916 KB Output is correct
7 Correct 2 ms 4952 KB Output is correct

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2096 ms 13652 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 240 ms 4952 KB Output is correct
2 Correct 255 ms 4956 KB Output is correct
3 Correct 244 ms 5160 KB Output is correct
4 Correct 2 ms 4956 KB Output is correct
5 Correct 2 ms 4956 KB Output is correct
6 Correct 2 ms 4956 KB Output is correct
7 Correct 239 ms 5160 KB Output is correct
8 Correct 476 ms 4956 KB Output is correct
9 Correct 121 ms 5156 KB Output is correct
10 Correct 448 ms 4952 KB Output is correct
11 Correct 236 ms 4956 KB Output is correct
12 Correct 2 ms 4952 KB Output is correct
13 Correct 2 ms 4956 KB Output is correct
14 Correct 3 ms 4952 KB Output is correct
15 Correct 2 ms 4956 KB Output is correct
16 Correct 2 ms 4956 KB Output is correct
17 Correct 2 ms 4956 KB Output is correct
18 Correct 2 ms 4956 KB Output is correct
19 Correct 129 ms 13648 KB Output is correct
20 Correct 153 ms 15696 KB Output is correct
21 Correct 129 ms 15916 KB Output is correct
22 Correct 2 ms 4952 KB Output is correct
23 Execution timed out 2096 ms 13652 KB Time limit exceeded
24 Halted 0 ms 0 KB -