QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #395891 | #63. Meetings | Rafi22 | 7 | 273ms | 4416kb | C++14 | 1.9kb | 2024-04-22 00:20:26 | 2024-04-22 00:20:26 |
Judging History
answer
#include <bits/stdc++.h>
#include "meetings.h"
//#define int long long
#define ll long long
#define ld long double
//#define endl '\n'
#define st first
#define nd second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
using namespace std;
int inf=1000000007;
ll infl=1000000000000000007;
ll mod=1000000007;
ll mod1=998244353;
const int N=2007;
set<int>G[N];
bool odw[N];
bool was[N];
int s[N];
void del(int u,int v)
{
G[v].erase(u);
G[u].erase(v);
//cout<<"DEL "<<u<<" "<<v<<endl;
}
void add(int u,int v)
{
G[v].insert(u);
G[u].insert(v);
//cout<<"ADD "<<u<<" "<<v<<endl;
}
void dfs(int v,int o)
{
s[v]=1;
for(auto u:G[v])
{
if(u==o||odw[u]) continue;
dfs(u,v);
s[v]+=s[u];
}
}
void Solve(int n)
{
vector<int>V;
for(int i=0;i<n;i++) V.pb(i);
random_shuffle(all(V));
add(V[0],V[1]);
for(int i=2;i<n;i++)
{
if(was[V[i]]) continue;
memset(odw,0,sizeof odw);
int r=V[0];
//cout<<"XD "<<V[i]<<endl;
int xd=1;
while(true)
{
xd++;
if(xd>15) exit(2137);
dfs(r,0);
int v=r;
while(true)
{
int nx=-1;
for(auto u:G[v]) if(!odw[u]&&s[u]>i/2&&s[u]<s[v]) nx=u;
if(nx==-1) break;
v=nx;
}
odw[v]=1;
//cout<<v<<endl;
vector<pair<int,int>>X;
for(auto u:G[v]) if(!odw[u]) X.pb({s[u],u});
sort(all(X),greater<pair<int,int>>());
bool is=0,is1=0;
for(auto [k,u]:X)
{
int t=Query(v,u,V[i]);
if(t!=v)
{
if(t==u)
{
r=u;
is1=1;
}
else if(t==V[i])
{
is=1;
del(u,v);
add(u,V[i]);
add(V[i],v);
}
else
{
is=1;
del(u,v);
add(u,t);
add(t,v);
add(t,V[i]);
was[t]=1;
}
break;
}
}
if(is) break;
if(!is1)
{
add(v,V[i]);
break;
}
}
}
for(int u=0;u<n;u++) for(auto v:G[u]) if(u<v) Bridge(u,v);
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 7
Accepted
Test #1:
score: 7
Accepted
time: 0ms
memory: 4200kb
input:
3 0 2 0 1
output:
Accepted: 1
result:
ok 1 move(s)
Test #2:
score: 0
Accepted
time: 1ms
memory: 3896kb
input:
4 1 2 0 2 0 3
output:
Accepted: 3
result:
ok 3 move(s)
Test #3:
score: 0
Accepted
time: 0ms
memory: 3960kb
input:
4 0 3 2 3 0 1
output:
Accepted: 2
result:
ok 2 move(s)
Test #4:
score: 0
Accepted
time: 0ms
memory: 3956kb
input:
5 2 4 2 3 0 2 1 3
output:
Accepted: 4
result:
ok 4 move(s)
Test #5:
score: 0
Accepted
time: 0ms
memory: 3888kb
input:
5 3 4 0 1 0 2 0 3
output:
Accepted: 3
result:
ok 3 move(s)
Test #6:
score: 0
Accepted
time: 0ms
memory: 4224kb
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: 4228kb
input:
6 2 4 0 1 0 2 0 5 3 4
output:
Accepted: 8
result:
ok 8 move(s)
Test #8:
score: 0
Accepted
time: 0ms
memory: 3908kb
input:
7 1 4 0 6 0 5 1 2 0 3 0 4
output:
Accepted: 8
result:
ok 8 move(s)
Test #9:
score: 0
Accepted
time: 0ms
memory: 4228kb
input:
7 0 4 1 4 2 3 2 4 0 6 2 5
output:
Accepted: 5
result:
ok 5 move(s)
Test #10:
score: 0
Accepted
time: 0ms
memory: 4200kb
input:
7 3 5 4 5 0 2 2 6 1 2 1 5
output:
Accepted: 7
result:
ok 7 move(s)
Test #11:
score: 0
Accepted
time: 0ms
memory: 3964kb
input:
7 3 6 5 6 4 6 1 6 2 6 0 6
output:
Accepted: 13
result:
ok 13 move(s)
Test #12:
score: 0
Accepted
time: 0ms
memory: 3960kb
input:
7 2 3 0 5 4 6 1 6 0 2 3 4
output:
Accepted: 10
result:
ok 10 move(s)
Test #13:
score: 0
Accepted
time: 0ms
memory: 3896kb
input:
7 5 6 1 2 4 5 2 3 3 4 0 1
output:
Accepted: 8
result:
ok 8 move(s)
Subtask #2:
score: 0
Runtime Error
Dependency #1:
100%
Accepted
Test #14:
score: 10
Accepted
time: 1ms
memory: 3924kb
input:
50 25 32 16 48 36 46 13 48 18 27 18 30 9 29 19 47 30 35 2 36 1 49 33 34 41 47 11 13 7 10 17 38 2 18 1 15 1 33 4 23 8 11 36 47 14 20 25 39 5 7 12 48 2 45 21 47 0 21 1 23 19 43 32 33 4 14 22 36 38 46 5 28 1 29 2 31 3 4 40 47 34 44 34 42 24 43 33 36 11 26 6 11 7 47 37 38 1 6
output:
Accepted: 191
result:
ok 191 move(s)
Test #15:
score: 0
Accepted
time: 1ms
memory: 3972kb
input:
49 10 47 29 42 18 38 21 45 11 17 8 34 8 46 27 31 29 32 14 30 5 28 36 41 20 24 17 27 13 45 3 38 7 34 1 8 27 40 0 7 22 34 11 23 13 28 14 35 24 47 3 43 2 33 0 37 18 44 3 7 2 26 4 17 23 41 28 30 3 17 28 32 17 26 16 31 6 17 19 30 9 25 4 12 42 48 17 28 17 47 17 39 2 15 7 25
output:
Accepted: 228
result:
ok 228 move(s)
Test #16:
score: 0
Accepted
time: 1ms
memory: 3968kb
input:
48 6 19 1 33 34 44 29 30 27 35 8 40 17 39 8 47 11 46 14 40 17 32 8 23 26 40 9 27 4 8 11 39 33 38 8 15 21 40 2 41 7 11 20 26 12 28 16 24 31 41 18 24 34 46 0 40 34 38 5 15 10 34 18 45 26 29 40 43 35 47 6 21 28 34 8 41 8 42 14 18 22 30 3 14 34 37 13 46 14 36 17 25 8 46
output:
Accepted: 217
result:
ok 217 move(s)
Test #17:
score: 0
Accepted
time: 1ms
memory: 4212kb
input:
50 15 16 25 42 41 42 31 48 44 45 7 43 7 30 1 19 13 26 0 23 4 38 18 49 40 41 8 42 7 38 14 33 18 19 2 47 3 15 1 3 30 47 3 7 1 26 20 38 21 36 3 25 39 42 28 45 3 45 6 8 33 48 6 17 25 35 29 47 12 29 1 34 21 46 17 37 41 46 3 22 5 45 1 31 7 24 32 38 11 30 27 36 0 39 3 9 10 20
output:
Accepted: 183
result:
ok 183 move(s)
Test #18:
score: 0
Accepted
time: 1ms
memory: 3896kb
input:
50 29 46 2 21 3 16 22 31 11 49 2 43 36 40 7 17 1 46 30 32 42 49 5 15 7 44 6 12 20 46 23 30 21 23 26 27 28 34 7 10 6 20 38 42 39 45 2 8 8 33 20 39 19 43 30 35 14 38 3 12 17 47 13 26 12 21 25 49 0 40 27 40 28 47 5 47 16 17 22 24 37 38 16 42 22 23 39 48 6 27 18 26 8 9 4 43 5 41
output:
Accepted: 164
result:
ok 164 move(s)
Test #19:
score: 0
Accepted
time: 1ms
memory: 3976kb
input:
50 32 36 23 29 27 37 33 48 0 17 17 49 38 41 17 19 6 17 20 29 27 38 10 29 12 36 11 40 16 48 36 38 11 38 30 48 27 34 11 15 29 38 17 38 35 48 9 48 13 36 18 48 3 11 4 48 29 42 11 39 8 29 11 28 17 24 5 27 31 36 36 43 29 47 27 46 14 17 11 44 22 36 21 36 7 17 29 45 11 25 2 27 1 27 26 27 38 48
output:
Accepted: 287
result:
ok 287 move(s)
Test #20:
score: 0
Accepted
time: 0ms
memory: 3964kb
input:
49 24 42 4 21 2 21 12 48 16 24 24 45 6 21 21 46 21 23 20 24 22 24 21 38 14 24 12 25 24 30 21 24 12 39 31 32 0 31 11 21 12 37 12 36 9 31 18 24 24 47 24 35 7 24 12 27 13 21 12 33 12 21 5 12 21 41 3 12 21 31 24 26 12 29 10 12 24 28 24 44 1 21 17 21 8 12 12 15 24 34 19 21 12 40 12 43
output:
Accepted: 401
result:
ok 401 move(s)
Test #21:
score: 0
Accepted
time: 1ms
memory: 4212kb
input:
50 10 36 39 42 23 39 8 39 24 43 24 46 10 17 33 39 10 38 10 41 10 45 10 40 10 16 28 39 10 24 14 39 4 24 18 39 7 39 26 39 10 44 1 24 21 24 9 24 13 39 10 31 39 48 24 37 24 35 19 24 10 27 39 49 25 39 2 24 39 47 10 20 24 39 3 10 0 24 10 29 6 24 10 12 22 24 10 30 34 39 15 24 10 11 24 32 5 10
output:
Accepted: 454
result:
ok 454 move(s)
Test #22:
score: 0
Accepted
time: 1ms
memory: 4248kb
input:
50 14 29 13 43 13 37 13 40 5 14 1 13 22 34 13 24 13 23 3 14 2 13 34 41 14 36 18 34 31 34 34 45 13 39 14 21 14 19 13 33 14 20 34 46 13 32 15 34 0 14 34 35 14 42 14 25 13 49 11 13 34 44 13 28 7 34 14 34 4 34 13 47 14 38 9 14 6 34 26 34 8 13 13 14 27 34 14 16 13 17 10 13 14 48 12 14 30 34
output:
Accepted: 413
result:
ok 413 move(s)
Test #23:
score: 0
Accepted
time: 1ms
memory: 3960kb
input:
50 3 20 11 12 9 33 17 24 13 49 5 36 10 47 4 48 41 44 14 16 9 48 6 16 12 18 6 30 2 23 2 40 31 41 1 17 3 21 25 37 34 39 44 49 19 42 7 27 7 15 20 35 18 24 14 32 1 32 9 43 0 29 22 38 34 38 12 21 42 48 17 31 29 45 22 49 8 42 28 34 10 11 10 37 4 32 3 5 13 27 5 26 14 46 16 29 2 46
output:
Accepted: 168
result:
ok 168 move(s)
Test #24:
score: -10
Runtime Error
input:
50 20 46 25 39 4 22 8 17 10 47 1 23 41 48 14 20 15 39 4 21 45 49 13 45 33 42 34 35 36 41 29 31 30 44 29 32 3 32 16 49 27 38 27 47 0 10 8 37 9 18 9 43 0 44 11 25 12 31 37 46 5 19 28 43 13 17 6 21 28 40 23 26 2 24 33 48 2 18 5 40 7 30 6 16 1 19 24 34 14 42 7 26 15 22 11 12 3 35
output:
Unauthorized output
result:
Subtask #3:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
0%
Subtask #4:
score: 0
Runtime Error
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Dependency #3:
100%
Accepted
Test #40:
score: 71
Accepted
time: 273ms
memory: 4416kb
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:
Accepted: 17957
result:
ok 17957 move(s)
Test #41:
score: 0
Runtime Error
input:
2000 708 1863 9 1590 217 1903 135 249 1413 1878 189 1114 697 1866 314 643 149 1872 816 1309 91 1784 73 1965 525 1062 390 947 121 929 242 1450 486 1229 688 736 759 1972 16 1778 458 983 1139 1168 78 1742 1386 1487 460 514 1704 1896 206 649 1325 1580 365 445 100 1325 51 324 1955 1983 820 1183 90 1264 3...
output:
Unauthorized output