#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 ban, int pre)
{
//printf("now=%d\n", now);
g[now].clear();
sub[now]=1;
for(int nxt : v[now])
{
if(nxt==ban || nxt==pre) continue;
dfs1(nxt, ban, 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 ban, int pre)
{
//printf("2now=%d\n", now);
g[now].clear();
sub[now]=1;
for(int nxt : v[now])
{
if(nxt==ban || nxt==pre) continue;
dfs2(nxt, ban, 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, ban=-1;
int cnt=0;
while(true)
{
cnt++;
assert(cnt<=10);
dfs1(root, ban, -1);
int cent=root;
while(!g[cent].empty() && sub[g[cent][0]]*2>sub[cent]) cent=g[cent][0];
dfs2(cent, ban, -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;
ban=cent;
}
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:69:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
69 | for(int j=0;j<g[cent].size();j++)
| ~^~~~~~~~~~~~~~~
meetings.cpp:79:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
79 | for(int k=0;k<v[cent].size();k++) if(v[cent][k]==nxt) v[cent][k]=i;
| ~^~~~~~~~~~~~~~~
meetings.cpp:80:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
80 | for(int k=0;k<v[nxt].size();k++) if(v[nxt][k]==cent) v[nxt][k]=i;
| ~^~~~~~~~~~~~~~
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[cent].size();k++) if(v[cent][k]==nxt) v[cent][k]=res;
| ~^~~~~~~~~~~~~~~
meetings.cpp:95:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
95 | 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 |
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 |
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 |
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 |
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 |
2 ms |
748 KB |
Execution killed with signal 6 |
15 |
Halted |
0 ms |
0 KB |
- |
# |
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 |
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 |
2 ms |
748 KB |
Execution killed with signal 6 |
15 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
4 ms |
1132 KB |
Execution killed with signal 6 |
2 |
Halted |
0 ms |
0 KB |
- |