#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=0; 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){
if(find(link[x].begin(), link[x].end(), y) == link[x].end()) exit(1);
if(find(link[y].begin(), link[y].end(), x) == link[y].end()) exit(1);
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, r = q;
else if(ret == vec[p]) r = p;
else l = q;
}
delEdge(vec[l], vec[r]);
addEdge(vec[l], i);
addEdge(vec[r], i);
break;
}
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){
down[c] = down[y];
swap(y, child[c][0]);
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, r = q;
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);
break;
}
}
}
for(int i=0; i<n; i++){
for(auto j: link[i]){
if(i<j){
// printf("Bridge %d %d\n", i, j);
Bridge(i, j);
}
}
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
492 KB |
Output is correct |
2 |
Correct |
1 ms |
492 KB |
Output is correct |
3 |
Correct |
1 ms |
492 KB |
Output is correct |
4 |
Correct |
1 ms |
492 KB |
Output is correct |
5 |
Correct |
1 ms |
492 KB |
Output is correct |
6 |
Correct |
1 ms |
512 KB |
Output is correct |
7 |
Correct |
1 ms |
492 KB |
Output is correct |
8 |
Correct |
1 ms |
492 KB |
Output is correct |
9 |
Correct |
1 ms |
492 KB |
Output is correct |
10 |
Correct |
1 ms |
492 KB |
Output is correct |
11 |
Correct |
1 ms |
492 KB |
Output is correct |
12 |
Correct |
1 ms |
492 KB |
Output is correct |
13 |
Correct |
1 ms |
492 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
492 KB |
Output is correct |
2 |
Correct |
1 ms |
492 KB |
Output is correct |
3 |
Correct |
1 ms |
492 KB |
Output is correct |
4 |
Correct |
1 ms |
492 KB |
Output is correct |
5 |
Correct |
1 ms |
492 KB |
Output is correct |
6 |
Correct |
1 ms |
512 KB |
Output is correct |
7 |
Correct |
1 ms |
492 KB |
Output is correct |
8 |
Correct |
1 ms |
492 KB |
Output is correct |
9 |
Correct |
1 ms |
492 KB |
Output is correct |
10 |
Correct |
1 ms |
492 KB |
Output is correct |
11 |
Correct |
1 ms |
492 KB |
Output is correct |
12 |
Correct |
1 ms |
492 KB |
Output is correct |
13 |
Correct |
1 ms |
492 KB |
Output is correct |
14 |
Correct |
1 ms |
492 KB |
Output is correct |
15 |
Correct |
1 ms |
492 KB |
Output is correct |
16 |
Correct |
1 ms |
492 KB |
Output is correct |
17 |
Correct |
1 ms |
492 KB |
Output is correct |
18 |
Correct |
1 ms |
492 KB |
Output is correct |
19 |
Correct |
1 ms |
492 KB |
Output is correct |
20 |
Correct |
1 ms |
492 KB |
Output is correct |
21 |
Correct |
1 ms |
492 KB |
Output is correct |
22 |
Correct |
1 ms |
492 KB |
Output is correct |
23 |
Correct |
1 ms |
492 KB |
Output is correct |
24 |
Correct |
1 ms |
492 KB |
Output is correct |
25 |
Correct |
1 ms |
492 KB |
Output is correct |
26 |
Correct |
1 ms |
492 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
492 KB |
Output is correct |
2 |
Correct |
1 ms |
492 KB |
Output is correct |
3 |
Correct |
1 ms |
492 KB |
Output is correct |
4 |
Correct |
1 ms |
492 KB |
Output is correct |
5 |
Correct |
1 ms |
492 KB |
Output is correct |
6 |
Correct |
1 ms |
512 KB |
Output is correct |
7 |
Correct |
1 ms |
492 KB |
Output is correct |
8 |
Correct |
1 ms |
492 KB |
Output is correct |
9 |
Correct |
1 ms |
492 KB |
Output is correct |
10 |
Correct |
1 ms |
492 KB |
Output is correct |
11 |
Correct |
1 ms |
492 KB |
Output is correct |
12 |
Correct |
1 ms |
492 KB |
Output is correct |
13 |
Correct |
1 ms |
492 KB |
Output is correct |
14 |
Correct |
1 ms |
492 KB |
Output is correct |
15 |
Correct |
1 ms |
492 KB |
Output is correct |
16 |
Correct |
1 ms |
492 KB |
Output is correct |
17 |
Correct |
1 ms |
492 KB |
Output is correct |
18 |
Correct |
1 ms |
492 KB |
Output is correct |
19 |
Correct |
1 ms |
492 KB |
Output is correct |
20 |
Correct |
1 ms |
492 KB |
Output is correct |
21 |
Correct |
1 ms |
492 KB |
Output is correct |
22 |
Correct |
1 ms |
492 KB |
Output is correct |
23 |
Correct |
1 ms |
492 KB |
Output is correct |
24 |
Correct |
1 ms |
492 KB |
Output is correct |
25 |
Correct |
1 ms |
492 KB |
Output is correct |
26 |
Correct |
1 ms |
492 KB |
Output is correct |
27 |
Correct |
16 ms |
620 KB |
Output is correct |
28 |
Correct |
13 ms |
620 KB |
Output is correct |
29 |
Correct |
12 ms |
620 KB |
Output is correct |
30 |
Correct |
15 ms |
620 KB |
Output is correct |
31 |
Correct |
9 ms |
620 KB |
Output is correct |
32 |
Correct |
14 ms |
620 KB |
Output is correct |
33 |
Correct |
18 ms |
620 KB |
Output is correct |
34 |
Correct |
21 ms |
620 KB |
Output is correct |
35 |
Correct |
24 ms |
620 KB |
Output is correct |
36 |
Correct |
13 ms |
620 KB |
Output is correct |
37 |
Correct |
12 ms |
620 KB |
Output is correct |
38 |
Correct |
13 ms |
620 KB |
Output is correct |
39 |
Correct |
4 ms |
620 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1016 ms |
1688 KB |
Output is correct |
2 |
Correct |
960 ms |
1632 KB |
Output is correct |
3 |
Correct |
995 ms |
1668 KB |
Output is correct |
4 |
Correct |
1231 ms |
1964 KB |
Output is correct |
5 |
Correct |
808 ms |
1672 KB |
Output is correct |
6 |
Correct |
942 ms |
1772 KB |
Output is correct |
7 |
Correct |
989 ms |
1516 KB |
Output is correct |
8 |
Correct |
1225 ms |
1516 KB |
Output is correct |
9 |
Correct |
1087 ms |
1644 KB |
Output is correct |
10 |
Correct |
1035 ms |
1560 KB |
Output is correct |
11 |
Correct |
1161 ms |
1516 KB |
Output is correct |
12 |
Execution timed out |
3091 ms |
4204 KB |
Time limit exceeded |
13 |
Halted |
0 ms |
0 KB |
- |