#include <bits/stdc++.h>
#include "meetings.h"
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<ull, ull> pull;
typedef pair<int, int> pii;
typedef pair<ld, ld> pld;
int p[2009];
vector<int> sub[2009];
int done[2009];
vector<int> cur;
int prt[2009];
void dfs(int v){
done[v] = 1;
for(auto u : sub[v])
if(done[u] == 0)
dfs(u);
cur.pb(v);
}
void calc(vector<int> all){
if(all.size() <= 1) return;
vector<vector<int>> groups;
int root = all.back();
done[root] = 1;
for(auto u : all){
if(done[u]) continue;
for(auto &v : groups){
int tmp = Query(root, v.back(), u);
if(tmp == root)
continue;
if(u != tmp)
sub[tmp].pb(u);
if(v.back() != tmp)
sub[tmp].pb(v.back());
cur.clear();
dfs(tmp);
v.insert(v.end(), cur.begin(), cur.end());
break;
}
if(done[u] == 0){
cur.clear();
dfs(u);
groups.pb(cur);
}
}
for(auto u : all) done[u] = 0;
for(auto v : groups){
p[v.back()] = root;
calc(v);
}
}
void Solve(int n){
vector<int> all;
for(int i = n-1; i >= 0; --i)
all.pb(i);
calc(all);
for(int i = 1; i < n; ++i){
//cout << i << ' ' << p[i] << '\n';
Bridge(min(i, p[i]), max(i, p[i]));
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
504 KB |
Output is correct |
2 |
Correct |
5 ms |
376 KB |
Output is correct |
3 |
Correct |
5 ms |
376 KB |
Output is correct |
4 |
Correct |
5 ms |
376 KB |
Output is correct |
5 |
Correct |
6 ms |
376 KB |
Output is correct |
6 |
Correct |
5 ms |
504 KB |
Output is correct |
7 |
Correct |
5 ms |
376 KB |
Output is correct |
8 |
Correct |
5 ms |
504 KB |
Output is correct |
9 |
Correct |
5 ms |
424 KB |
Output is correct |
10 |
Correct |
4 ms |
376 KB |
Output is correct |
11 |
Correct |
5 ms |
376 KB |
Output is correct |
12 |
Correct |
5 ms |
504 KB |
Output is correct |
13 |
Correct |
5 ms |
376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
504 KB |
Output is correct |
2 |
Correct |
5 ms |
376 KB |
Output is correct |
3 |
Correct |
5 ms |
376 KB |
Output is correct |
4 |
Correct |
5 ms |
376 KB |
Output is correct |
5 |
Correct |
6 ms |
376 KB |
Output is correct |
6 |
Correct |
5 ms |
504 KB |
Output is correct |
7 |
Correct |
5 ms |
376 KB |
Output is correct |
8 |
Correct |
5 ms |
504 KB |
Output is correct |
9 |
Correct |
5 ms |
424 KB |
Output is correct |
10 |
Correct |
4 ms |
376 KB |
Output is correct |
11 |
Correct |
5 ms |
376 KB |
Output is correct |
12 |
Correct |
5 ms |
504 KB |
Output is correct |
13 |
Correct |
5 ms |
376 KB |
Output is correct |
14 |
Correct |
5 ms |
504 KB |
Output is correct |
15 |
Correct |
5 ms |
376 KB |
Output is correct |
16 |
Correct |
5 ms |
376 KB |
Output is correct |
17 |
Correct |
5 ms |
376 KB |
Output is correct |
18 |
Correct |
5 ms |
376 KB |
Output is correct |
19 |
Correct |
5 ms |
376 KB |
Output is correct |
20 |
Correct |
5 ms |
376 KB |
Output is correct |
21 |
Correct |
5 ms |
504 KB |
Output is correct |
22 |
Correct |
5 ms |
504 KB |
Output is correct |
23 |
Correct |
5 ms |
376 KB |
Output is correct |
24 |
Correct |
5 ms |
376 KB |
Output is correct |
25 |
Correct |
5 ms |
376 KB |
Output is correct |
26 |
Correct |
5 ms |
376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
504 KB |
Output is correct |
2 |
Correct |
5 ms |
376 KB |
Output is correct |
3 |
Correct |
5 ms |
376 KB |
Output is correct |
4 |
Correct |
5 ms |
376 KB |
Output is correct |
5 |
Correct |
6 ms |
376 KB |
Output is correct |
6 |
Correct |
5 ms |
504 KB |
Output is correct |
7 |
Correct |
5 ms |
376 KB |
Output is correct |
8 |
Correct |
5 ms |
504 KB |
Output is correct |
9 |
Correct |
5 ms |
424 KB |
Output is correct |
10 |
Correct |
4 ms |
376 KB |
Output is correct |
11 |
Correct |
5 ms |
376 KB |
Output is correct |
12 |
Correct |
5 ms |
504 KB |
Output is correct |
13 |
Correct |
5 ms |
376 KB |
Output is correct |
14 |
Correct |
5 ms |
504 KB |
Output is correct |
15 |
Correct |
5 ms |
376 KB |
Output is correct |
16 |
Correct |
5 ms |
376 KB |
Output is correct |
17 |
Correct |
5 ms |
376 KB |
Output is correct |
18 |
Correct |
5 ms |
376 KB |
Output is correct |
19 |
Correct |
5 ms |
376 KB |
Output is correct |
20 |
Correct |
5 ms |
376 KB |
Output is correct |
21 |
Correct |
5 ms |
504 KB |
Output is correct |
22 |
Correct |
5 ms |
504 KB |
Output is correct |
23 |
Correct |
5 ms |
376 KB |
Output is correct |
24 |
Correct |
5 ms |
376 KB |
Output is correct |
25 |
Correct |
5 ms |
376 KB |
Output is correct |
26 |
Correct |
5 ms |
376 KB |
Output is correct |
27 |
Correct |
18 ms |
504 KB |
Output is correct |
28 |
Correct |
14 ms |
484 KB |
Output is correct |
29 |
Correct |
14 ms |
504 KB |
Output is correct |
30 |
Correct |
15 ms |
504 KB |
Output is correct |
31 |
Correct |
14 ms |
376 KB |
Output is correct |
32 |
Correct |
16 ms |
376 KB |
Output is correct |
33 |
Correct |
21 ms |
380 KB |
Output is correct |
34 |
Correct |
23 ms |
376 KB |
Output is correct |
35 |
Correct |
21 ms |
376 KB |
Output is correct |
36 |
Correct |
17 ms |
504 KB |
Output is correct |
37 |
Correct |
85 ms |
888 KB |
Output is correct |
38 |
Correct |
126 ms |
1272 KB |
Output is correct |
39 |
Correct |
185 ms |
1400 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1117 ms |
1144 KB |
Output is correct |
2 |
Correct |
1103 ms |
1144 KB |
Output is correct |
3 |
Correct |
1115 ms |
1016 KB |
Output is correct |
4 |
Correct |
1272 ms |
1144 KB |
Output is correct |
5 |
Correct |
1102 ms |
1400 KB |
Output is correct |
6 |
Correct |
849 ms |
1272 KB |
Output is correct |
7 |
Correct |
842 ms |
888 KB |
Output is correct |
8 |
Correct |
976 ms |
916 KB |
Output is correct |
9 |
Correct |
874 ms |
1016 KB |
Output is correct |
10 |
Correct |
854 ms |
1144 KB |
Output is correct |
11 |
Correct |
940 ms |
892 KB |
Output is correct |
12 |
Execution timed out |
3089 ms |
3576 KB |
Time limit exceeded |
13 |
Halted |
0 ms |
0 KB |
- |