# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
899741 | YassirSalama | ICC (CEOI16_icc) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <iomanip>
#include <cmath>
#include <limits>
#include <map>
#include <utility>
#include <cctype>
#include <string>
#include <cstring>
#include <stack>
#include <queue>
#include<assert.h>
#include <functional>
#include <iterator>
#include "icc.h"
using namespace std;
#define OVL(x,s) for(auto y:x) cout<<y<<s; cout<<"\n";
#ifdef IOI
void dbg_out() { cout << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cout << ' ' << H; dbg_out(T...); }
#define dbg(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__);
#else
#define dbg(...) 1337;
#endif
#define endl "\n"
#define pb push_back
#define F first
#define S second
#define ll long long
#define mod 1000000007
#define all(v) v.begin(),v.end()
int ask(vector<int> a,vector<int> b){
int n=a.size();
int m=b.size();
int A[n];
int B[m];
for(int i=0;i<n;i++) A[i]=a[i];
for(int i=0;i<m;i++) B[i]=b[i];
return query(n,m,A,B);
}
const int MAXN=2e3+100;
int par[MAXN];
struct DSU {
DSU(){
for(int i=0;i<MAXN;i++) par[i]=i;
}
int find(int node){
return node==par[node]?node:par[node]=find(par[node]);
}
bool same(int a,int b){
return find(a)==find(b);
}
void merge(int a,int b){
a=find(a);
b=find(b);
if(a==b) return;
par[a]=b;
}
};
void run(int n){
DSU dsu=DSU();
for(int ww=0;ww<n-1;ww++){
int x=-1;
int y=-1;
for(int i=1;i<=n;i++){
vector<int> a;
vector<int> b;
a.push_back(i);
for(int j=1;j<=n;j++){
if(i==j) continue;
if(dsu.same(i,j)) continue;
b.pb(j);
}
// dbg(i);
// OVL(a," ")
// OVL(b," ")
// dbg(ask(a,b))
if(ask(a,b)){
// dbg(i)
// OVL(b," ")
for(auto x:b){
vector<int> c;
c.pb(x);
// dbg(i,x,ask(a,c))
if(ask(a,c)){
// dbg(i,x)
setRoad(i,x);
dsu.merge(i,x);
// ok=true;
break;
}
}
break;
}
}
continue;
dbg(x,y)
setRoad(x,y);
dsu.merge(x,y);
// break;
// setRoad(1,1);
}
}
#ifdef IOI
int main(){
int n;
cin>>n;
vector<pair<int,int>> v;
for(int i=0;i<n-1;i++){
int a,b;
cin>>a>>b;
v.pb({a,b});
}
for(int i=0;i<MMS;i++) pr[i]=i;
EDGES=v;
mp[{EDGES[0].F,EDGES[0].S}]=1;
mp[{EDGES[0].S,EDGES[0].F}]=1;
merge(EDGES[0].F,EDGES[0].S);
run(n);
cout<<"YES"<<endl;
}
#elif
int main(){
return 0;
}
#endif