#include<bits/stdc++.h>
#include "meetings.h"
using namespace std;
#define X first
#define Y second
typedef pair<int,int> ii;
void wtf(int u,int v) {
if (u > v)
swap(u,v);
Bridge(u,v);
}
void calc(vector<int> Ver,int P) {
int n = Ver.size();
if (n == 1) {
wtf(Ver[0],P);
return;
}
int x = Ver[rand() % n];
vector<ii> Remain;
vector<int> toRoot(1,x);
for(int a : Ver) if (a != x) {
int u = Query(P,a,x);
if (u == a)
toRoot.push_back(u);
else
Remain.push_back({u,a});
}
sort(Remain.begin(),Remain.end());
sort(toRoot.begin(),toRoot.end(),[&](int x,int y) {
return Query(P,x,y) == x;
});
toRoot.erase(unique(toRoot.begin(),toRoot.end()),toRoot.end());
for(int x : toRoot)
wtf(x,P),
P = x;
int l = 0;
int r = 0;
Ver.clear();
for(; l < Remain.size() ;) {
for(; r < Remain.size() && Remain[r].X == Remain[l].X ; ++r) Ver.push_back(Remain[r].Y);
calc(Ver, Remain[l].X);
l = r;
}
}
void Solve(int n) {
srand(time(NULL));
vector<int> Ver(n - 1);
iota(Ver.begin(),Ver.end(),1);
calc(Ver,0);
}
Compilation message
meetings.cpp: In function 'void calc(std::vector<int>, int)':
meetings.cpp:51:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(; l < Remain.size() ;) {
~~^~~~~~~~~~~~~~~
meetings.cpp:52:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(; r < Remain.size() && Remain[r].X == Remain[l].X ; ++r) Ver.push_back(Remain[r].Y);
~~^~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
248 KB |
Output is correct |
3 |
Correct |
2 ms |
376 KB |
Output is correct |
4 |
Correct |
2 ms |
376 KB |
Output is correct |
5 |
Incorrect |
2 ms |
376 KB |
Wrong Answer [4] |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
248 KB |
Output is correct |
3 |
Correct |
2 ms |
376 KB |
Output is correct |
4 |
Correct |
2 ms |
376 KB |
Output is correct |
5 |
Incorrect |
2 ms |
376 KB |
Wrong Answer [4] |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
248 KB |
Output is correct |
3 |
Correct |
2 ms |
376 KB |
Output is correct |
4 |
Correct |
2 ms |
376 KB |
Output is correct |
5 |
Incorrect |
2 ms |
376 KB |
Wrong Answer [4] |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
88 ms |
504 KB |
Wrong Answer [4] |
2 |
Halted |
0 ms |
0 KB |
- |