#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
namespace{
int n;
vector<int> link[2002];
bool found[2002];
vector<int> child[2002];
int sz[2002], down[2002];
int par[2002];
void dfs_sz(int x, int pr=-1){
sz[x] = 1;
for(auto &y: link[x]){
if(y == pr) continue;
child[x].push_back(y);
par[y] = x;
dfs_sz(y, x);
if(sz[y] > sz[child[x][0]]) swap(y, child[x][0]);
}
}
void dfs_hld(int x){
down[x] = x;
for(auto y: child[x]){
dfs_hld(y);
if(y == child[x][0]) down[x] = down[y];
}
}
int init(){
for(int i=1; i<=n; i++){
child[i].clear();
}
int c = 0;
dfs_sz(c);
dfs_hld(c);
return c;
}
void addEdge(int x, int y){
link[x].push_back(y);
link[y].push_back(x);
found[x] = found[y] = 1;
}
void delEdge(int x, int y){
link[x].erase(find(link[x].begin(), link[x].end(), y));
link[y].erase(find(link[y].begin(), link[y].end(), x));
}
struct dat{
int x, y, z;
dat(){}
dat(int _x, int _y, int _z){
x = min({_x, _y, _z});
z = max({_x, _y, _z});
y = _x ^ _y ^ _z ^ x ^ z;
}
bool operator<(const dat &r)const{
return make_pair(x, make_pair(y, z)) < make_pair(r.x, make_pair(r.y, r.z));
}
};
map<dat, int> mp;
int query(int x, int y, int z){
if(mp[dat(x, y, z)]) return mp[dat(x, y, z)];
return mp[dat(x, y, z)] = Query(x, y, z);
}
}
void Solve(int N){
n = N;
found[0] = 1;
for(int i=1; i<n; i++){ /// 위치를 찾을 정점의 번호
if(found[i]) continue;
int c = init();
while(true){
if(c == down[c]){
addEdge(c, i);
break;
}
int tmp = query(c, down[c], i);
if(tmp == down[c]){
addEdge(down[c], i);
break;
}
else if(tmp == i){
vector<int> vec;
vec.push_back(down[c]);
while(vec.back() != c) vec.push_back(par[vec.back()]);
int l = 0, r = (int)vec.size()-1;
while(l < r-1){
int p = (l+l+r)/3;
int q = (l+r+r)/3;
int ret = query(vec[p], vec[q], i);
if(ret == i) l = p;
else if(ret == vec[p]) r = p;
else l = q;
}
delEdge(vec[l], vec[r]);
addEdge(vec[l], i);
addEdge(vec[r], i);
}
else if(tmp == c){ /// c의 다른 자식과 연결되어 있을 것이다.
bool done = 0;
for(auto y: child[c]){
if(y == child[c][0]) continue;
if(Query(c, down[y], i) != c){
c = y;
done = 1;
break;
}
}
if(!done){
addEdge(c, i);
break;
}
}
else if(found[tmp]){
c = tmp;
}
else{ /// 마지막 케이스: 새로운 정점이 발견되었다.
vector<int> vec;
vec.push_back(down[c]);
while(vec.back() != c) vec.push_back(par[vec.back()]);
int l = 0, r = (int)vec.size()-1;
while(l < r-1){
int p = (l+l+r)/3;
int q = (l+r+r)/3;
int ret = query(vec[p], vec[q], tmp);
if(ret == tmp) l = p;
else if(ret == vec[p]) r = p;
else l = q;
}
delEdge(vec[l], vec[r]);
addEdge(vec[l], tmp);
addEdge(vec[r], tmp);
addEdge(tmp, i);
}
}
}
for(int i=0; i<n; i++){
for(auto j: link[i]){
if(i<j) Bridge(i, j);
}
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
492 KB |
Output is correct |
2 |
Runtime error |
2 ms |
876 KB |
Execution killed with signal 11 |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
492 KB |
Output is correct |
2 |
Runtime error |
2 ms |
876 KB |
Execution killed with signal 11 |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
492 KB |
Output is correct |
2 |
Runtime error |
2 ms |
876 KB |
Execution killed with signal 11 |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
180 ms |
262148 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |