#include "meetings.h"
#include <bits/stdc++.h>
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 f[mxN];
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 nxt : v[now])
{
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 nxt : v[now])
{
if(Chk[nxt] || nxt==pre) continue;
dfs2(nxt, now);
sub[now]+=sub[nxt];
g[now].push_back(nxt);
}
}
void Solve(int N) {
for(int i=0;i<N;i++) f[i]=(i+N/2)%N;
v[0].push_back(1);
v[1].push_back(0);
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 par=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(f[cent], f[nxt], f[i])-N/2+N)%N;
if(res!=cent)
{
par=false;
if(res==i)
{
//printf("s1");
for(int k=0;k<v[cent].size();k++)
{
if(v[cent][k]==nxt)
{
v[cent][k]=i;
break;
}
}
for(int k=0;k<v[nxt].size();k++)
{
if(v[nxt][k]==cent)
{
v[nxt][k]=i;
break;
}
}
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");
for(int k=0;k<v[cent].size();k++)
{
if(v[cent][k]==nxt)
{
v[cent][k]=res;
break;
}
}
for(int k=0;k<v[nxt].size();k++)
{
if(v[nxt][k]==cent)
{
v[nxt][k]=res;
break;
}
}
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(par)
{
v[cent].push_back(i);
v[i].push_back(cent);
break;
}
}
}
for(int i=0;i<N;i++)
{
for(int nxt : v[i])
{
if(nxt>i) Bridge(f[i], f[nxt]);
}
}
}
Compilation message
meetings.cpp: In function 'void Solve(int)':
meetings.cpp:78:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
78 | for(int j=0;j<g[cent].size();j++)
| ~^~~~~~~~~~~~~~~
meetings.cpp:88:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
88 | for(int k=0;k<v[cent].size();k++)
| ~^~~~~~~~~~~~~~~
meetings.cpp:96:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
96 | for(int k=0;k<v[nxt].size();k++)
| ~^~~~~~~~~~~~~~
meetings.cpp:118:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
118 | for(int k=0;k<v[cent].size();k++)
| ~^~~~~~~~~~~~~~~
meetings.cpp:126:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
126 | for(int k=0;k<v[nxt].size();k++)
| ~^~~~~~~~~~~~~~
meetings.cpp:54:13: warning: unused variable 'cnt' [-Wunused-variable]
54 | int cnt=0;
| ^~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
492 KB |
Wrong Answer [3] |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
492 KB |
Wrong Answer [3] |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
492 KB |
Wrong Answer [3] |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1517 ms |
1004 KB |
Wrong Answer [3] |
2 |
Halted |
0 ms |
0 KB |
- |