oj.uz

Submission #579856

# Submission time Handle Problem Language Result Execution time Memory
579856 2022-06-20T06:35:55 Z Mr_Husanboy Love Polygon (BOI18_polygon) C++14
25 / 100
 294 ms 19276 KB 
// Muallif: Mansuraliyev Husanboy Murotali o'g'li  >> NamPS
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>

using namespace std;

#define ll long long
#define ios ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define all(a) a.begin(), a.end()
#define F first
#define rep(x,start,end) for(auto x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define S second
#define fp(a,i,c) for(int (a) = (i); (a) < (c); (a)++)
#define fm(a,i,c) for(int (a) = (i); (a) >= (c); (a)--)
// 0-9 >> 48-57;    A-Z>>65-90   and   a-z>>97-122 respectively;

const int MX=1e5+5;

vector<int> g[MX];
int vis[MX];

int dfs(int i){
	vis[i]=1;
	int s=0;
	for(auto u:g[i]){
		if(vis[u]==1){
			continue;
		}
		s+=dfs(u)+1;
	}
	vis[i]=2;
	return s;
}


void solve(){
	int n; cin>>n;
	map<string,int> mp;
	int cur=1;
	for(int i=0;i<n;i++){
		string a,b; cin>>a>>b;
		if(mp[a]==0) mp[a]=cur,cur++;
		if(mp[b]==0) mp[b]=cur,cur++;
		g[mp[a]].push_back(mp[b]);
	}
	if(n%2){
		cout<<"-1\n";return;
	}
	int k=0;
	ll ans=0;
	for(int i=1;i<=n;i++){
		if(vis[i]) continue;
		int s=dfs(i)+1;
		k+=s%2;
		if(s!=2)
		ans+=s/2;
	}
	cout<<ans+k<<"\n";
}
	

int main(){
	ios;
	solve();
}

Subtask #1
0 / 21.0

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

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 242 ms 18856 KB Output is correct
5 Correct 243 ms 16056 KB Output is correct
6 Correct 246 ms 19276 KB Output is correct
7 Correct 196 ms 15692 KB Output is correct

Subtask #3
0 / 29.0

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

Subtask #4
0 / 25.0

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