#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
typedef long long int ll;
typedef vector<ll> vi;
typedef pair<ll,ll> pi;
#define ff first
#define ss second
#define all(a) a.begin(),a.end()
#define fip(a,b) for(ll i = a; i < b ; i++)
#define fjp(a,b) for(ll j = a; j < b ; j++)
#define fp(k,a,b) for(ll k = a; k < b ; k++)
#define fin(a,b) for(ll i = a; i >= b ; i--)
#define fjn(a,b) for(ll i = a; j >= b ; j--)
#define fn(k,a,b) for(ll k = a; k >= b ; k--)
#define fx(a) for(auto x : a)
#define ordered_set tree<pi,null_type,less<pi>,rb_tree_tag,tree_order_statistics_node_update>
#define total_one(k) __builtin_popcount(k)
#define back_zero(k) __builtin_ctzll(k)
#define front_zero(k) __builtin_clzll(k)
#define nli "\n"
ll n,m,ans,sum,res,cnt,tptp,tp,tp2;
const ll mx = 1e5 + 5;
const ll mod = 1e9 + 7;
unordered_map<string,ll> hashe;
string k1,k2;
vi adj[mx];
vi reverse_adj[mx];
bool vis[mx];
ll find_root(ll k){
if(adj[k].front() == k)
return k;
fx(adj[k])
return find_root(x);
}
ll dfs(ll u,ll root){
vis[u] = 1;
ll sz = 1;
fx(reverse_adj[u])
if(!vis[x]){
sz += dfs(x,root);
}
if(sz>=2){
ans += sz - 1;
sz = 0;
}
if(sz==1 && u == root){
ans++;
}
return sz;
}
int main(){
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
// #ifdef code
// freopen("input1.txt","r",stdin);
// freopen("output1.txt","w",stdout);
// freopen("error1.txt","w",stderr);
// #endif
cin>>n;
tptp = 0;
ans = 0;
cnt = 0;
fip(1,n+1){
cin>>k1>>k2;
if(!hashe.count(k1)){
cnt++;
hashe[k1] = cnt;
}
if(!hashe.count(k2)){
cnt++;
hashe[k2] = cnt;
}
adj[hashe[k1]].push_back(hashe[k2]);
reverse_adj[hashe[k2]].push_back(hashe[k1]);
}
if(n&1){
cout<<-1<<nli;
return 0;
}
fip(1,n+1){
if(!vis[i]){
tptp = find_root(i);
dfs(tptp,tptp);
}
}
cout<<ans<<nli;
// cerr << "Time elapsed : " << setprecision(6) << 100.00 * clock() / CLOCKS_PER_SEC << "ms\n";
}
Compilation message
polygon.cpp: In function 'll find_root(ll)':
polygon.cpp:41:1: warning: control reaches end of non-void function [-Wreturn-type]
41 | }
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 2 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 3 |
Correct |
3 ms |
5032 KB |
Output is correct |
| 4 |
Execution timed out |
2067 ms |
4948 KB |
Time limit exceeded |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 2 |
Execution timed out |
2060 ms |
4948 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
152 ms |
18468 KB |
Output is correct |
| 2 |
Correct |
181 ms |
21968 KB |
Output is correct |
| 3 |
Correct |
92 ms |
21148 KB |
Output is correct |
| 4 |
Correct |
109 ms |
19688 KB |
Output is correct |
| 5 |
Correct |
162 ms |
26860 KB |
Output is correct |
| 6 |
Correct |
167 ms |
19828 KB |
Output is correct |
| 7 |
Correct |
129 ms |
19800 KB |
Output is correct |
| 8 |
Correct |
108 ms |
20044 KB |
Output is correct |
| 9 |
Correct |
103 ms |
19588 KB |
Output is correct |
| 10 |
Correct |
78 ms |
18764 KB |
Output is correct |
| 11 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 12 |
Correct |
4 ms |
4948 KB |
Output is correct |
| 13 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 14 |
Correct |
4 ms |
5028 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 2 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 3 |
Correct |
3 ms |
5032 KB |
Output is correct |
| 4 |
Execution timed out |
2067 ms |
4948 KB |
Time limit exceeded |
| 5 |
Halted |
0 ms |
0 KB |
- |
