| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 369726 |
2021-02-22T09:14:23 Z |
79brue |
Meetings (JOI19_meetings) |
C++14 |
|
210 ms |
262148 KB |
#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);
sz[x] += sz[y];
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();
}
memset(sz, 0, sizeof(sz));
memset(down, 0, sizeof(down));
memset(par, 0, sizeof(par));
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));
}
map<ll, int> mp;
int queryCnt = 0;
int query(int x, int y, int z){
ll hashCode = ll(x) * 1e12 + ll(y) * 1e6 + ll(z);
if(mp[hashCode]) return mp[hashCode];
assert(++queryCnt <= 40000);
return mp[hashCode] = 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();
int tcnt = 0;
while(true){
assert(++tcnt <= 100);
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의 다른 자식과 연결되어 있을 것이다.
tmp1:
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;
goto tmp1;
}
else{ /// 마지막 케이스: 새로운 정점이 발견되었다.
vector<int> vec;
vec.push_back(down[c]);
int tcnt = 0;
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);
}
}
}
}
Compilation message
meetings.cpp: In function 'void Solve(int)':
meetings.cpp:140:21: warning: unused variable 'tcnt' [-Wunused-variable]
140 | int tcnt = 0;
| ^~~~
| # |
Verdict |
Execution time |
Memory |
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 |
492 KB |
Output is correct |
| 7 |
Incorrect |
1 ms |
492 KB |
Wrong Answer [5] |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
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 |
492 KB |
Output is correct |
| 7 |
Incorrect |
1 ms |
492 KB |
Wrong Answer [5] |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
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 |
492 KB |
Output is correct |
| 7 |
Incorrect |
1 ms |
492 KB |
Wrong Answer [5] |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
210 ms |
262148 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
