#include "meetings.h"
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
using namespace std;
#define fir first
#define sec second
const int mxN=2020;
vector <int> v[mxN], g[mxN];
int msub[mxN];
bool Chk[mxN];
bool used[mxN];
int sub[mxN];
int par[mxN][mxN];
int findpar(int a, int b)
{
if(par[a][b]==b) return b;
return par[a][b]=findpar(a, par[a][b]);
}
bool cmp1(int a, int b)
{
return sub[a]>sub[b];
}
void dfs1(int now, int pre)
{
//printf("now=%d\n", now);
g[now].clear();
sub[now]=1;
msub[now]=-1;
for(int pnxt : v[now])
{
int nxt=findpar(now, pnxt);
if(Chk[nxt] || nxt==pre) continue;
dfs1(nxt, now);
sub[now]+=sub[nxt];
if(msub[now]==-1) msub[now]=nxt;
else if(sub[msub[now]]<sub[nxt]) msub[now]=nxt;
}
}
void dfs2(int now, int pre)
{
//printf("2now=%d\n", now);
g[now].clear();
sub[now]=1;
for(int pnxt : v[now])
{
int nxt=findpar(now, pnxt);
if(Chk[nxt] || nxt==pre) continue;
dfs2(nxt, now);
sub[now]+=sub[nxt];
g[now].push_back(nxt);
}
}
void Solve(int N) {
v[0].push_back(1);
v[1].push_back(0);
for(int i=0;i<N;i++) for(int j=0;j<N;j++) par[i][j]=j;
for(int i=2;i<N;i++)
{
if(used[i]) continue;
int root=i-1;
for(int j=0;j<N;j++) Chk[j]=false;
int cnt=0;
while(true)
{
dfs1(root, -1);
int cent=root;
while(!g[cent].empty() && sub[msub[cent]]*2>sub[cent]) cent=g[cent][0];
dfs2(cent, -1);
//printf("cent=%d\n", cent);
//for(int j=0;j<i;j++) printf("Chk[%d]=%d\n", j, Chk[j]);
/*for(int j=0;j<i;j++)
{
printf("%d: ", j);
for(int nxt : g[j]) printf("%d ", nxt);
printf("\n");
}*/
if(g[cent].empty())
{
v[cent].push_back(i);
v[i].push_back(cent);
break;
}
bool ispar=true;
bool flag=false;
sort(g[cent].begin(), g[cent].end(), cmp1);
for(int j=0;j<g[cent].size();j++)
{
int nxt=g[cent][j];
int res=Query(cent, nxt, i);
if(res!=cent)
{
ispar=false;
if(res==i)
{
//printf("s1");
par[cent][nxt]=i;
par[nxt][cent]=i;
v[i].push_back(cent);
v[i].push_back(nxt);
flag=true;
}
else if(res==nxt)
{
//printf("s2");
root=nxt;
Chk[cent]=true;
//assert(cent!=nxt);
}
else
{
//printf("s3");
par[cent][nxt]=res;
par[nxt][cent]=res;
v[res].push_back(cent);
v[res].push_back(nxt);
v[i].push_back(res);
v[res].push_back(i);
used[res]=true;
flag=true;
}
break;
}
}
if(flag) break;
if(ispar)
{
v[cent].push_back(i);
v[i].push_back(cent);
break;
}
}
}
for(int i=0;i<N;i++)
{
for(int pnxt : v[i])
{
int nxt=findpar(i, pnxt);
if(nxt>i) Bridge(i, nxt);
}
}
}
Compilation message
meetings.cpp: In function 'void Solve(int)':
meetings.cpp:88:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
88 | for(int j=0;j<g[cent].size();j++)
| ~^~~~~~~~~~~~~~~
meetings.cpp:64:13: warning: unused variable 'cnt' [-Wunused-variable]
64 | int cnt=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 |
Correct |
1 ms |
492 KB |
Output is correct |
8 |
Correct |
1 ms |
492 KB |
Output is correct |
9 |
Correct |
1 ms |
512 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 |
# |
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 |
Correct |
1 ms |
492 KB |
Output is correct |
8 |
Correct |
1 ms |
492 KB |
Output is correct |
9 |
Correct |
1 ms |
512 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 |
748 KB |
Output is correct |
15 |
Correct |
1 ms |
748 KB |
Output is correct |
16 |
Correct |
1 ms |
620 KB |
Output is correct |
17 |
Correct |
1 ms |
748 KB |
Output is correct |
18 |
Correct |
1 ms |
748 KB |
Output is correct |
19 |
Correct |
1 ms |
748 KB |
Output is correct |
20 |
Correct |
2 ms |
640 KB |
Output is correct |
21 |
Correct |
1 ms |
748 KB |
Output is correct |
22 |
Correct |
1 ms |
748 KB |
Output is correct |
23 |
Correct |
1 ms |
748 KB |
Output is correct |
24 |
Correct |
2 ms |
748 KB |
Output is correct |
25 |
Correct |
1 ms |
748 KB |
Output is correct |
26 |
Correct |
1 ms |
748 KB |
Output is correct |
# |
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 |
Correct |
1 ms |
492 KB |
Output is correct |
8 |
Correct |
1 ms |
492 KB |
Output is correct |
9 |
Correct |
1 ms |
512 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 |
748 KB |
Output is correct |
15 |
Correct |
1 ms |
748 KB |
Output is correct |
16 |
Correct |
1 ms |
620 KB |
Output is correct |
17 |
Correct |
1 ms |
748 KB |
Output is correct |
18 |
Correct |
1 ms |
748 KB |
Output is correct |
19 |
Correct |
1 ms |
748 KB |
Output is correct |
20 |
Correct |
2 ms |
640 KB |
Output is correct |
21 |
Correct |
1 ms |
748 KB |
Output is correct |
22 |
Correct |
1 ms |
748 KB |
Output is correct |
23 |
Correct |
1 ms |
748 KB |
Output is correct |
24 |
Correct |
2 ms |
748 KB |
Output is correct |
25 |
Correct |
1 ms |
748 KB |
Output is correct |
26 |
Correct |
1 ms |
748 KB |
Output is correct |
27 |
Correct |
22 ms |
2028 KB |
Output is correct |
28 |
Correct |
22 ms |
2028 KB |
Output is correct |
29 |
Correct |
24 ms |
2156 KB |
Output is correct |
30 |
Correct |
23 ms |
2028 KB |
Output is correct |
31 |
Correct |
23 ms |
2176 KB |
Output is correct |
32 |
Correct |
19 ms |
2028 KB |
Output is correct |
33 |
Correct |
23 ms |
2028 KB |
Output is correct |
34 |
Correct |
27 ms |
2028 KB |
Output is correct |
35 |
Correct |
25 ms |
2028 KB |
Output is correct |
36 |
Correct |
30 ms |
2028 KB |
Output is correct |
37 |
Correct |
188 ms |
2156 KB |
Output is correct |
38 |
Correct |
187 ms |
2156 KB |
Output is correct |
39 |
Correct |
4 ms |
2156 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
2494 ms |
17192 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |