oj.uz

Submission #916629

# Submission time Handle Problem Language Result Execution time Memory
916629 2024-01-26T07:35:27 Z LCJLY Love Polygon (BOI18_polygon) C++14
0 / 100
 227 ms 11112 KB 
#include <bits/stdc++.h>
using namespace std;
 
#define int long long
#define ld long double
#define show(x,y) cout << y << " " << #x << endl;
#define show2(x,y,i,j) cout << y << " " << #x << "  " << j << " " << #i << endl;
#define show3(x,y,i,j,p,q) cout << y << " " << #x << "  " << j << " " << #i << "  " << q << " " << #p << endl; 
#define show4(x,y) for(auto it:x) cout << it << " "; cout << #y << endl;
typedef pair<int,int>pii;

int pp[100005];
map<string,int>mp;
int ptr=0;
int sz=0;
bool visited[100005];
bool visited2[100005];
int in[100005];

void dfs(int index){
	sz++;
	visited[index]=true;
	int nx=pp[index];
	if(visited[nx]) return;
	dfs(nx);
}

void solve(){
	int n;
	cin >> n;
	string s,s2;
	for(int x=0;x<n;x++){
		cin >> s >> s2;
		if(mp.find(s)==mp.end()){
			mp[s]=ptr++;
		}
		if(mp.find(s2)==mp.end()){
			mp[s2]=ptr++;
		}
		pp[mp[s]]=mp[s2];
		pp[mp[s2]]=mp[s];
		in[mp[s]]++;
	}
	
	int counter=0;
	queue<int>q;
	for(int x=0;x<n;x++){
		if(in[x]==0) q.push(x);
	}
	
	while(!q.empty()){
		int cur=q.front();
		q.pop();
		if(visited[cur]) continue;
		visited[cur]=true;
		int nx=pp[cur];
		in[nx]--;
		if(in[nx]==0){
			counter++;
			q.push(pp[nx]);
		}
		else{
			counter++;
			q.push(nx);
		}
	}
	
	for(int x=0;x<n;x++){
		if(visited[x]) continue;
		sz=0;
		dfs(x);
		if(sz==2) continue;
		counter+=(sz+1)/2;
	}
	if(n%2) cout << -1;
	else cout << counter;
}

int32_t main(){										
	ios::sync_with_stdio(0);	
	cin.tie(0);
	int t=1;
	//cin >> t;
	while(t--){
		solve();
	}
}

Subtask #1
0 / 21.0

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

Subtask #2
0 / 25.0

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

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 188 ms 11092 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

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