#include "meetings.h"
#include<bits/stdc++.h>
#define pb push_back
using namespace std;
const int maxn = 2e3 + 4;
int L[maxn][maxn];
int LCA(int u , int v){
if(u == 0 || v == 0)return 0;
if(u == v)return u;
if(u > v)swap(u , v);
if(L[u][v] != -1)return L[u][v];
return L[u][v] = Query(0 , u , v);
}
void Solve(vector<int> child){
// for(int c : child)cout << c << " ";cout << endl;
if(child.size() <= 1)return;
map<int,vector<int>> mmap;
srand(time(0));
int u = child[rand() % child.size()];
vector<int> can;
for(int c : child){
int a = LCA(c , u);
if(a == c)
can.pb(c);
mmap[a].pb(c);
}
sort(can.begin(),can.end(),[&](const int & x , const int & y){
return LCA(x , y) == x;
});
for(int i = 0 ; i < (int)can.size() - 1 ; ++i){
Bridge(min(can[i] , can[i + 1]) , max(can[i] , can[i + 1]));
}
for(auto& c : mmap)Solve(c.second);
}
void Solve(int n) {
memset(L,-1,sizeof L);
vector<int> v(n);
for(int i = 0 ; i < n ; ++i)v[i] = i;
Solve(v);
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
16120 KB |
Output is correct |
2 |
Correct |
15 ms |
16040 KB |
Output is correct |
3 |
Correct |
911 ms |
139128 KB |
Output is correct |
4 |
Correct |
910 ms |
139008 KB |
Output is correct |
5 |
Correct |
15 ms |
15992 KB |
Output is correct |
6 |
Correct |
826 ms |
127220 KB |
Output is correct |
7 |
Runtime error |
1737 ms |
262144 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
8 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
16120 KB |
Output is correct |
2 |
Correct |
15 ms |
16040 KB |
Output is correct |
3 |
Correct |
911 ms |
139128 KB |
Output is correct |
4 |
Correct |
910 ms |
139008 KB |
Output is correct |
5 |
Correct |
15 ms |
15992 KB |
Output is correct |
6 |
Correct |
826 ms |
127220 KB |
Output is correct |
7 |
Runtime error |
1737 ms |
262144 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
8 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
16120 KB |
Output is correct |
2 |
Correct |
15 ms |
16040 KB |
Output is correct |
3 |
Correct |
911 ms |
139128 KB |
Output is correct |
4 |
Correct |
910 ms |
139008 KB |
Output is correct |
5 |
Correct |
15 ms |
15992 KB |
Output is correct |
6 |
Correct |
826 ms |
127220 KB |
Output is correct |
7 |
Runtime error |
1737 ms |
262144 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
8 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
3022 ms |
187916 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |