QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #462211 | #63. Meetings | snpmrnhlol | 0 | 0ms | 4180kb | C++14 | 4.2kb | 2024-07-03 15:42:59 | 2024-07-03 15:43:00 |
answer
#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 2e3;
const int mod = 998244853;
const int inf = 2e9;
int rng = 123456;
int genrandom(){
rng = (1ll*rng*101 + 29)%mod;
return rng;
}
vector <int> e[N];
vector <int> nr;
int bad[N];
bool vis[N];
int sub[N];
void addedge(int x,int u,int w){
vis[x] = 1;
nr.push_back(x);
//cout<<"addedge:"<<x<<' '<<u<<' '<<w<<'\n';
if(w == -1){
e[u].push_back(x);
e[x].push_back(u);
return;
}else{
for(int i = 0;i < e[u].size();i++){
if(e[u][i] == w){
swap(e[u][i],e[u].back());
e[u].pop_back();
break;
}
}
swap(u,w);
for(int i = 0;i < e[u].size();i++){
if(e[u][i] == w){
swap(e[u][i],e[u].back());
e[u].pop_back();
break;
}
}
e[u].push_back(x);
e[x].push_back(u);
e[x].push_back(w);
e[w].push_back(x);
}
}
void cendecomp(int x, int node = nr[0]){
int sz = 0;
int cen = -1,cennr = inf;
auto dfs = [&](auto self, int node, int p) -> void{
sz++;
sub[node] = 1;
for(auto i:e[node]){
if(i == p || bad[i])continue;
self(self, i, node);
sub[node]+=sub[i];
}
};
auto dfs2 = [&](auto self, int node, int p) -> void{
int mx = -1;
for(auto i:e[node]){
if(i == p || bad[i])continue;
self(self, i, node);
if(mx < sub[i]){
mx = sub[i];
}
}
if(mx < sz - sub[node]){
mx = sz - sub[node];
}
if(cennr > mx){
cennr = mx;
cen = node;
}
};
sz = 0;
dfs(dfs, node, -1);
dfs2(dfs2, node, -1);
dfs(dfs, cen, -1);
vector <int> cands;
for(auto i:e[cen]){
if(bad[i])continue;
cands.push_back(i);
}
sort(cands.begin(),cands.end(),[&](int a, int b){
return sub[a] > sub[b];
});
if(cands.empty()){
///fuck it i give up
addedge(x,cen,-1);
return;
}/*cout<<"centroid:"<<cen<<'\n';
for(int i = 0;i < (int)cands.size();i++){
cout<<cands[i]<<' ';
}
cout<<'\n';*/
bad[cen] = 1;
for(int i = 0;i < (int)cands.size() - 1;i+=2){
int p = Query(cands[i],cands[i + 1],x);
if(p == cands[i] || p == cands[i + 1]){
cendecomp(x, p);
return;
}else if(p == x){
///what the fuck
int q = Query(cands[i],cen,x);
if(q == x){
addedge(x,cands[i],cen);
}else if(q == cen){
addedge(x,cands[i + 1],cen);
}else{
///fcuk
assert(0);
}
return;
}else if(p != cen){
assert(0);
return;
}
}
if(0 && cands.size()%2 == 0){
addedge(x,cen,-1);
}else{
int p = Query(cands[(int)cands.size() - 1],cen,x);
if(p == x){
addedge(x,cands[(int)cands.size() - 1],cen);
}else if(p == cands[(int)cands.size() - 1]){
cendecomp(x, cands[(int)cands.size() - 1]);
}else if(p == cen){
addedge(x,cen,-1);
}else{
addedge(p, cands[(int)cands.size() - 1], cen);
}
}
}
void add(int x){
if(nr.empty()){
nr.push_back(x);
vis[x] = 1;
return;
}else if(nr.size() == 1){
addedge(x,nr[0],-1);
return;
}
//cout<<"add:"<<x<<'\n';
for(int i = 0;i < nr.size();i++){
//cout<<nr[i]<<' ';
bad[nr[i]] = 0;
}
//cout<<'\n';
cendecomp(x);
}
void Solve(int n){
while(nr.size() < n){
for(int i = 0;i < n;i++){
if(!vis[i]){
add(i);
}
}
}
for(int i = 0;i < n;i++){
for(auto j:e[i]){
if(i < j){
//cout<<i<<' '<<j<<'\n';
Bridge(i, j);
}
}
}
}
/**
5
0 1
0 2
1 3
1 4
**/
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Runtime Error
Test #1:
score: 7
Accepted
time: 0ms
memory: 3900kb
input:
3 0 2 0 1
output:
Accepted: 1
result:
ok 1 move(s)
Test #2:
score: 0
Accepted
time: 0ms
memory: 4168kb
input:
4 1 2 0 2 0 3
output:
Accepted: 2
result:
ok 2 move(s)
Test #3:
score: 0
Accepted
time: 0ms
memory: 3964kb
input:
4 0 3 2 3 0 1
output:
Accepted: 3
result:
ok 3 move(s)
Test #4:
score: 0
Accepted
time: 0ms
memory: 3880kb
input:
5 2 4 2 3 0 2 1 3
output:
Accepted: 5
result:
ok 5 move(s)
Test #5:
score: 0
Accepted
time: 0ms
memory: 3836kb
input:
5 3 4 0 1 0 2 0 3
output:
Accepted: 5
result:
ok 5 move(s)
Test #6:
score: 0
Accepted
time: 0ms
memory: 4180kb
input:
6 1 5 2 4 0 4 1 3 3 4
output:
Accepted: 6
result:
ok 6 move(s)
Test #7:
score: 0
Accepted
time: 0ms
memory: 4132kb
input:
6 2 4 0 1 0 2 0 5 3 4
output:
Accepted: 6
result:
ok 6 move(s)
Test #8:
score: 0
Accepted
time: 0ms
memory: 3880kb
input:
7 1 4 0 6 0 5 1 2 0 3 0 4
output:
Accepted: 9
result:
ok 9 move(s)
Test #9:
score: 0
Accepted
time: 0ms
memory: 4180kb
input:
7 0 4 1 4 2 3 2 4 0 6 2 5
output:
Accepted: 9
result:
ok 9 move(s)
Test #10:
score: -7
Runtime Error
input:
7 3 5 4 5 0 2 2 6 1 2 1 5
output:
Unauthorized output
result:
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 0
Skipped
Dependency #1:
0%
Subtask #4:
score: 0
Runtime Error
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Dependency #3:
100%
Accepted
Test #40:
score: 0
Runtime Error
input:
2000 58 503 623 1403 1004 1083 249 491 1524 1849 192 562 1261 1877 547 909 267 896 747 1986 381 1329 57 317 779 886 469 1652 628 1456 1732 1790 700 825 494 1799 1450 1733 103 1069 1114 1342 243 1496 930 1361 240 905 398 1737 1008 1765 357 954 1157 1898 1228 1344 1062 1731 160 1977 40 364 343 694 108...
output:
Unauthorized output