#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
const int N=305;
int ans[N][N][N];
vector<int> adj[N];
int ask(int i,int j,int k)
{
if(ans[i][j][k]!=-1) return ans[i][j][k];
return ans[i][j][k]=ans[i][k][j]=ans[j][i][k]=ans[j][k][i]=ans[k][i][j]=ans[k][j][i]=Query(i,j,k);
}
void solve(int root,vector<int> cur)
{
int vid[N];
vector<int> v[N];
int cursz=1;
for(int i=0;i<cur.size();i++)
{
for(int j=i+1;j<cur.size();j++)
{
int x=cur[i],y=cur[j];
if(ask(root,x,y)==root) continue;
if(vid[x]==0&&vid[y]==0)
{
vid[x]=vid[y]=cursz++;
v[cursz-1].push_back(x);
v[cursz-1].push_back(y);
}
if(!vid[x])
{
v[vid[y]].push_back(x);
vid[x]=vid[y];
}
if(!vid[y])
{
v[vid[x]].push_back(y);
vid[y]=vid[x];
}
}
}
for(int i:cur)
{
if(!vid[i])
{
adj[i].push_back(root);
adj[root].push_back(i);
}
}
for(int i=1;i<cursz;i++)
{
for(int j=0;j<v[i].size();j++)
{
int sz=0;
for(int k=0;k<v[i].size();k++)
{
if(k==j) continue;
sz+=(ask(root,v[i][j],v[i][k])==v[i][j]);
}
if(sz==v[i].size()-1)
{
adj[root].push_back(v[i][j]);
adj[v[i][j]].push_back(root);
int nroot=v[i][j];
v[i].erase(v[i].begin()+j);
if(v[i].size())
solve(nroot,v[i]);
break;
}
}
}
}
void Solve(int n) {
memset(ans,-1,sizeof ans);
vector<int> v;
for(int i=1;i<n;i++) v.push_back(i);
solve(0,v);
for(int i=0;i<n;i++)
for(int j:adj[i])
if(i<j)
Bridge(i,j);
}
Compilation message
meetings.cpp: In function 'void solve(int, std::vector<int>)':
meetings.cpp:22:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<cur.size();i++)
~^~~~~~~~~~~
meetings.cpp:24:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=i+1;j<cur.size();j++)
~^~~~~~~~~~~
meetings.cpp:56:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=0;j<v[i].size();j++)
~^~~~~~~~~~~~
meetings.cpp:59:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int k=0;k<v[i].size();k++)
~^~~~~~~~~~~~
meetings.cpp:64:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(sz==v[i].size()-1)
~~^~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
94 ms |
111352 KB |
Output is correct |
2 |
Correct |
94 ms |
111352 KB |
Output is correct |
3 |
Correct |
95 ms |
111480 KB |
Output is correct |
4 |
Correct |
94 ms |
111352 KB |
Output is correct |
5 |
Correct |
94 ms |
111480 KB |
Output is correct |
6 |
Correct |
94 ms |
111476 KB |
Output is correct |
7 |
Correct |
95 ms |
111480 KB |
Output is correct |
8 |
Correct |
107 ms |
111432 KB |
Output is correct |
9 |
Correct |
93 ms |
111352 KB |
Output is correct |
10 |
Correct |
93 ms |
111352 KB |
Output is correct |
11 |
Correct |
93 ms |
111352 KB |
Output is correct |
12 |
Correct |
94 ms |
111352 KB |
Output is correct |
13 |
Correct |
93 ms |
111480 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
94 ms |
111352 KB |
Output is correct |
2 |
Correct |
94 ms |
111352 KB |
Output is correct |
3 |
Correct |
95 ms |
111480 KB |
Output is correct |
4 |
Correct |
94 ms |
111352 KB |
Output is correct |
5 |
Correct |
94 ms |
111480 KB |
Output is correct |
6 |
Correct |
94 ms |
111476 KB |
Output is correct |
7 |
Correct |
95 ms |
111480 KB |
Output is correct |
8 |
Correct |
107 ms |
111432 KB |
Output is correct |
9 |
Correct |
93 ms |
111352 KB |
Output is correct |
10 |
Correct |
93 ms |
111352 KB |
Output is correct |
11 |
Correct |
93 ms |
111352 KB |
Output is correct |
12 |
Correct |
94 ms |
111352 KB |
Output is correct |
13 |
Correct |
93 ms |
111480 KB |
Output is correct |
14 |
Correct |
100 ms |
111480 KB |
Output is correct |
15 |
Correct |
96 ms |
111540 KB |
Output is correct |
16 |
Correct |
99 ms |
111480 KB |
Output is correct |
17 |
Correct |
98 ms |
111480 KB |
Output is correct |
18 |
Correct |
98 ms |
111468 KB |
Output is correct |
19 |
Correct |
96 ms |
111480 KB |
Output is correct |
20 |
Correct |
96 ms |
111352 KB |
Output is correct |
21 |
Correct |
97 ms |
111352 KB |
Output is correct |
22 |
Correct |
96 ms |
111388 KB |
Output is correct |
23 |
Correct |
100 ms |
111612 KB |
Output is correct |
24 |
Correct |
107 ms |
111736 KB |
Output is correct |
25 |
Correct |
103 ms |
111760 KB |
Output is correct |
26 |
Correct |
110 ms |
111860 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
94 ms |
111352 KB |
Output is correct |
2 |
Correct |
94 ms |
111352 KB |
Output is correct |
3 |
Correct |
95 ms |
111480 KB |
Output is correct |
4 |
Correct |
94 ms |
111352 KB |
Output is correct |
5 |
Correct |
94 ms |
111480 KB |
Output is correct |
6 |
Correct |
94 ms |
111476 KB |
Output is correct |
7 |
Correct |
95 ms |
111480 KB |
Output is correct |
8 |
Correct |
107 ms |
111432 KB |
Output is correct |
9 |
Correct |
93 ms |
111352 KB |
Output is correct |
10 |
Correct |
93 ms |
111352 KB |
Output is correct |
11 |
Correct |
93 ms |
111352 KB |
Output is correct |
12 |
Correct |
94 ms |
111352 KB |
Output is correct |
13 |
Correct |
93 ms |
111480 KB |
Output is correct |
14 |
Correct |
100 ms |
111480 KB |
Output is correct |
15 |
Correct |
96 ms |
111540 KB |
Output is correct |
16 |
Correct |
99 ms |
111480 KB |
Output is correct |
17 |
Correct |
98 ms |
111480 KB |
Output is correct |
18 |
Correct |
98 ms |
111468 KB |
Output is correct |
19 |
Correct |
96 ms |
111480 KB |
Output is correct |
20 |
Correct |
96 ms |
111352 KB |
Output is correct |
21 |
Correct |
97 ms |
111352 KB |
Output is correct |
22 |
Correct |
96 ms |
111388 KB |
Output is correct |
23 |
Correct |
100 ms |
111612 KB |
Output is correct |
24 |
Correct |
107 ms |
111736 KB |
Output is correct |
25 |
Correct |
103 ms |
111760 KB |
Output is correct |
26 |
Correct |
110 ms |
111860 KB |
Output is correct |
27 |
Incorrect |
396 ms |
111480 KB |
Wrong Answer [2] |
28 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
256 ms |
225696 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |