#include "meetings.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <iostream>
#include <functional>
#include <unordered_set>
#include <bitset>
#include <time.h>
#include <limits.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define Fi first
#define Se second
#define pb push_back
#define szz(x) (int)x.size()
#define rep(i,n) for(int i=0;i<n;i++)
#define all(x) x.begin(),x.end()
typedef tuple<int, int, int> t3;
vector <pii> ans;
vector <int> E[2020];
int chk[2020], rt, down[2020], pp[2020];
int mark[2020];
void add_edge(int x, int y) { E[x].pb(y); E[y].pb(x); }
void del_edge(int x, int y) {
rep(i, szz(E[x])) if(E[x][i] == y) { swap(E[x][i], E[x].back()); E[x].pop_back(); break; }
rep(i, szz(E[y])) if(E[y][i] == x) { swap(E[y][i], E[y].back()); E[y].pop_back(); break; }
}
int Temp[2020], tp;
void pdfs(int x, int fa = -1) {
Temp[tp++] = x;
down[x] = 1;
for(int e : E[x]) if(e != fa && mark[e] == 0) {
pp[e] = x;
pdfs(e, x);
down[x] += down[e];
}
}
void solve(int rt, int x) {
if(chk[x]) return;
tp = 0; pdfs(rt);
int f1 = -1, f2 = -1, cnt = down[rt], fv = -1;
if(cnt == 1) {
add_edge(rt, x);
return;
}
rep(a, tp) if(Temp[a] != rt) {
int i = Temp[a];
if(min(down[i], cnt-down[i]) > fv) {
fv = min(down[i], cnt-down[i]);
f1 = i, f2 = pp[i];
}
}
int v = Query(f1, f2, x);
if(v != f1 && v != f2) {
del_edge(f1, f2);
add_edge(f1, v);
add_edge(f2, v);
if(x != v) add_edge(x, v);
chk[x] = chk[v] = 1;
return;
}
if(v == f1) {
mark[f2] = 1;
solve(f1, x);
}
else {
mark[f1] = 1;
solve(f2, x);
}
}
void Solve(int N) {
vector <int> X; rep(i, N) X.pb(i);
random_shuffle(all(X));
chk[rt=X[0]] = 1;
add_edge(X[0], X[1]);
for(int i=2;i<N;i++) { memset(mark, 0, sizeof mark); solve(X[0], X[i]); }
rep(i, N) for(int e : E[i]) if(i < e) Bridge(i, e), printf("%d %d\n", i, e);
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
2 ms |
504 KB |
DO NOT PRINT ANYTHING TO STANDARD OUTPUT |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
2 ms |
504 KB |
DO NOT PRINT ANYTHING TO STANDARD OUTPUT |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
2 ms |
504 KB |
DO NOT PRINT ANYTHING TO STANDARD OUTPUT |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
843 ms |
776 KB |
DO NOT PRINT ANYTHING TO STANDARD OUTPUT |
2 |
Halted |
0 ms |
0 KB |
- |