| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1363386 | sophiaeternalia | Social Engineering (EGOI22_socialengineering) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
/*map<pair<int, int>, int> mama;
int vv;
int nn;
int GetMove(){
if (vv!=1){
cout<<"WRONG GET_MOVE"<<"\n";
return -1;
}
for (int i=1; i<=nn; i++){
if (mama[{vv, i}]==1){
mama[{vv, i}]=0;
mama[{i, vv}]=0;
return i;
}
}
cout<<"YOU WON"<<"\n";
return 0;
}
void mamakeMove(int v){
if (mama[{v, vv}]==1){
vv=v;
mama[{v, vv}]=0;
mama[{vv, v}]=0;
} else {
vv=-1;
}
}*/
//-------------------------------------------------------------------------------------------------------------
vector<int> c;
vector<map<int, int>> g;
void dfsc(int v, int co){
c[v]=co;
for (auto u: g[v]){
if (u.second!=1){
continue;
}
if (c[u.first]==-1){
dfsc(u.first, co);
}
}
}
void SocialEngineering(int n, int m, vector<pair<int,int>> edges){
c.clear();
c.assign(n, -1);
g.clear();
g.resize(n);
for (auto u: edges){
u.first--;
u.second--;
g[u.first][u.second]=1;
g[u.second][u.first]=1;
}
for (int i=1; i<n; i++){
if (c[i]==-1){
dfsc(i, i);
}
}
vector<int> ne(n, 0);
for (int i=1; i<n; i++){
if (g[i][0]==0){
g[i].erase(0);
} else {
ne[c[i]]++;
}
}
for (auto u: ne){
if (u%2==1){
//cout<<"YOU LOSE AND YOU KNOW IT"<<"\n";
return;
}
}
int a=GetMove();
if (a==0){
return;
} else if (a==-1){
return;
} else {
//cout<<"YOU THINK YOU WIN"<<"\n";
return;
}
}
//--------------------------------------------------------------------------------------------------------------
/*int main(){
cin.tie(0); ios_base::sync_with_stdio(NULL);
int n, m;
cin>>n>>m;
nn=n;
vv=1;
vector<pair<int, int>> e(m);
for (int i=0; i<m; i++){
int a, b;
cin>>a>>b;
mama[{a, b}]=1;
mama[{b, a}]=1;
e[i]={a, b};
}
SocialEngineering(n, m, e);
}*/