#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];
bool Chk[mxN];
bool used[mxN];
int sub[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;
for(int nxt : v[now])
{
if(Chk[nxt] || nxt==pre) continue;
dfs1(nxt, now);
sub[now]+=sub[nxt];
if(g[now].empty()) g[now].push_back(nxt);
else if(sub[g[now][0]]<sub[nxt]) g[now][0]=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) {
v[0].push_back(1);
v[1].push_back(0);
for(int i=2;i<N;i++)
{
if(used[i]) continue;
int root=1;
for(int j=0;j<i;j++) Chk[j]=false;
while(true)
{
dfs1(root, -1);
int cent=root;
while(!g[cent].empty() && sub[g[cent][0]]*2>=sub[cent]) cent=g[cent][0];
dfs2(cent, -1);
if(g[cent].empty())
{
//printf("here");
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);
assert(g[cent].size()<=18);
for(int j=0;j<g[cent].size();j++)
{
int nxt=g[cent][j];
int res=Query(cent, nxt, i);
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;
for(int k=0;k<v[nxt].size();k++) if(v[nxt][k]==cent) v[nxt][k]=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");
for(int k=0;k<v[cent].size();k++) if(v[cent][k]==nxt) v[cent][k]=res;
for(int k=0;k<v[nxt].size();k++) if(v[nxt][k]==cent) v[nxt][k]=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(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(i, nxt);
}
}
}
Compilation message
meetings.cpp: In function 'void Solve(int)':
meetings.cpp:67:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
67 | for(int j=0;j<g[cent].size();j++)
| ~^~~~~~~~~~~~~~~
meetings.cpp:77:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
77 | for(int k=0;k<v[cent].size();k++) if(v[cent][k]==nxt) v[cent][k]=i;
| ~^~~~~~~~~~~~~~~
meetings.cpp:78:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
78 | for(int k=0;k<v[nxt].size();k++) if(v[nxt][k]==cent) v[nxt][k]=i;
| ~^~~~~~~~~~~~~~
meetings.cpp:93:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
93 | for(int k=0;k<v[cent].size();k++) if(v[cent][k]==nxt) v[cent][k]=res;
| ~^~~~~~~~~~~~~~~
meetings.cpp:94:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
94 | for(int k=0;k<v[nxt].size();k++) if(v[nxt][k]==cent) v[nxt][k]=res;
| ~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 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 |
492 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 |
0 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 |
492 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 |
Runtime error |
185 ms |
262148 KB |
Execution killed with signal 9 |
| 15 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 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 |
492 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 |
Runtime error |
185 ms |
262148 KB |
Execution killed with signal 9 |
| 15 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
26 ms |
1260 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
