| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1353727 | Francisco_Martin | Social Engineering (EGOI22_socialengineering) | C++20 | 0 ms | 0 KiB |
//EGOI 2022 Social Engineering
//https://qoj.ac/contest/2259/problem/5180
#include <bits/stdc++.h>
#include "socialengineering.h"
using namespace std;
using ll = long long;
using vll = vector<ll>;
const ll MAXN = 2e5+5;
vll uf(MAXN,-1), g[MAXN], path[MAXN]; vector<bool> vis(MAXN,false), good(MAXN,false);
ll ufind(ll v){
if(uf[v]<0) return v;
return uf[v]=ufind(uf[v]);
}
void unite(ll v,ll u){
v=ufind(v); u=ufind(u);
if(v==u) return;
if(uf[v]>uf[u]) swap(v,u);
uf[v]+=uf[u]; uf[u]=v;
}
ll dfs(ll v){
vis[v]=true; vll nodes;
for(auto u:g[v]) if(!vis[u]){
ll x=dfs(u);
if(x!=-1) nodes.push_back(x);
}
for(auto u:nodes) path[u].push_back(v);
if(good[v]) nodes.push_back(v);
for(int i=1; i<nodes.size(); i+=2){
ll a=nodes[i-1], b=nodes[i]; vll temp1=path[a], temp2=path[b];
reverse(temp1.begin(),temp1.end()); reverse(temp2.begin(),temp2.end());
for(auto u:temp1) if(u!=v) path[b].push_back(u);
for(auto u:temp2) if(u!=v) path[a].push_back(u);
if(b!=v) path[a].push_back(b);
if(a!=v) path[b].push_back(a);
}
return (((ll)nodes.size()&1)?nodes.back():-1);
}
void SocialEngineering(int n, int m, vector<pair<int,int>> edges){
for(auto [a,b]:edges){
if(a==1 || b==1) good[a+b-1]=true;
else g[a].push_back(b), g[b].push_back(a), unite(a,b);
}
vll cnt(n+1,0);
for(int i=2; i<=n; i++) if(good[i]) cnt[ufind(i)]++;
for(int i=2; i<=n; i++) if(cnt[i]%2==1) return;
for(int i=2; i<=n; i++) if(ufind(i)==i) dfs(i);
while(true){
ll v=GetMove();
if(v==0) return;
for(auto u:path[v]) MakeMove(u);
MakeMove(1);
}
}