# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
1170960 | bbartek | Meetings (JOI19_meetings) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#include "meetings.h"
using namespace std;
typedef long long ll;
#define st first
#define nd second
#define pb push_back
const int maxn = 2003;
bool polaczone[maxn];
vector<int> synowie[maxn];
vector<int> kolejnosc;
vector<pair<int,int>> wyniki;
bool porownaj(int a,int b){
return synowie[a].size() < synowie[b].size();
}
/*
void Bridge(int a,int b){
cout<<a<<" "<<b<<"\n";
}
vector<int> graf[maxn];
vector<int> odl(maxn);
void dfs(int v,int p){
odl[v] = odl[p]+1;
for(auto i : graf[v]){
if(i==p)
continue;
dfs(i,v);
}
}
int Query(int a,int b,int c){
graf[0] = {1,2};
graf[1] = {0,3};
graf[2] = {0};
graf[3] = {1,4};
graf[4] = {3};
int minimum = 1e9,ind;
for(int i=0;i<5;i++){
odl.clear();
dfs(i,8);
if(odl[a]+odl[b]+odl[c] < minimum){
minimum = odl[a]+odl[b]+odl[c];
ind = i;
}
}
return ind;
}
*/
void Solve(int n) { //Query(a,b,c)//Bridge(a,b)//
int x;
for(int i=1;i<n;i++){
for(int j=i+1;j<n;j++){
x = Query(0,i,j);
if(x == i){
synowie[i].pb(j);
//cout<<i<<" "<<j<<"\n";
}
else if(x == j){
synowie[j].pb(i);
//cout<<j<<" "<<i<<"\n";
}
}
kolejnosc.pb(i);
}
sort(kolejnosc.begin(),kolejnosc.end(),porownaj);
for(auto i : kolejnosc){
//cout<<i<<" ";
for(auto j : synowie[i]){
if(polaczone[j])
continue;
wyniki.pb({min(i,j),max(i,j)});
polaczone[j] = 1;
}
}
for(int i=1;i<n;i++){
if(!polaczone[i]){
wyniki.pb({0,1});
}
}
for(auto i : wyniki){
Bridge({i.st,i.nd});
}
return;
}
/*
int main(){
Solve(5);
return 0;
}
*/