# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
123707 |
2019-07-02T05:10:05 Z |
박상수(#3035) |
Meetings (JOI19_meetings) |
C++14 |
|
975 ms |
1032 KB |
#include "meetings.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <iostream>
#include <functional>
#include <unordered_set>
#include <bitset>
#include <time.h>
#include <limits.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define Fi first
#define Se second
#define pb push_back
#define szz(x) (int)x.size()
#define rep(i,n) for(int i=0;i<n;i++)
#define all(x) x.begin(),x.end()
typedef tuple<int, int, int> t3;
vector <pii> ans;
vector <int> E[2020];
int chk[2020], rt, down[2020], pp[2020];
int mark[2020];
void add_edge(int x, int y) { E[x].pb(y); E[y].pb(x); }
void del_edge(int x, int y) {
rep(i, szz(E[x])) if(E[x][i] == y) { swap(E[x][i], E[x].back()); E[x].pop_back(); break; }
rep(i, szz(E[y])) if(E[y][i] == x) { swap(E[y][i], E[y].back()); E[y].pop_back(); break; }
}
int Temp[2020], tp;
void pdfs(int x, int fa = -1) {
Temp[tp++] = x;
down[x] = 1;
for(int e : E[x]) if(e != fa && mark[e] == 0) {
pp[e] = x;
pdfs(e, x);
down[x] += down[e];
}
}
void solve(int rt, int x) {
if(chk[x]) return;
tp = 0; pdfs(rt);
int f1 = -1, f2 = -1, cnt = down[rt], fv = -1;
if(cnt == 1) {
add_edge(rt, x);
return;
}
rep(a, tp) if(Temp[a] != rt) {
int i = Temp[a];
if(min(down[i], cnt-down[i]) > fv) {
fv = min(down[i], cnt-down[i]);
f1 = i, f2 = pp[i];
}
}
int v = Query(f1, f2, x);
if(v != f1 && v != f2) {
del_edge(f1, f2);
add_edge(f1, v);
add_edge(f2, v);
if(x != v) add_edge(x, v);
chk[x] = chk[v] = 1;
return;
}
if(v == f1) {
mark[f2] = 1;
solve(f1, x);
}
else {
mark[f1] = 1;
solve(f2, x);
}
}
void Solve(int N) {
vector <int> X; rep(i, N) X.pb(i);
random_shuffle(all(X));
chk[rt=X[0]] = 1;
add_edge(X[0], X[1]);
for(int i=2;i<N;i++) { memset(mark, 0, sizeof mark); solve(X[0], X[i]); }
rep(i, N) for(int e : E[i]) if(i < e) Bridge(i, e);
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
504 KB |
Output is correct |
3 |
Correct |
2 ms |
504 KB |
Output is correct |
4 |
Correct |
2 ms |
376 KB |
Output is correct |
5 |
Correct |
2 ms |
376 KB |
Output is correct |
6 |
Correct |
2 ms |
376 KB |
Output is correct |
7 |
Correct |
2 ms |
376 KB |
Output is correct |
8 |
Correct |
2 ms |
504 KB |
Output is correct |
9 |
Correct |
2 ms |
380 KB |
Output is correct |
10 |
Correct |
2 ms |
376 KB |
Output is correct |
11 |
Correct |
2 ms |
376 KB |
Output is correct |
12 |
Correct |
2 ms |
380 KB |
Output is correct |
13 |
Correct |
2 ms |
376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
504 KB |
Output is correct |
3 |
Correct |
2 ms |
504 KB |
Output is correct |
4 |
Correct |
2 ms |
376 KB |
Output is correct |
5 |
Correct |
2 ms |
376 KB |
Output is correct |
6 |
Correct |
2 ms |
376 KB |
Output is correct |
7 |
Correct |
2 ms |
376 KB |
Output is correct |
8 |
Correct |
2 ms |
504 KB |
Output is correct |
9 |
Correct |
2 ms |
380 KB |
Output is correct |
10 |
Correct |
2 ms |
376 KB |
Output is correct |
11 |
Correct |
2 ms |
376 KB |
Output is correct |
12 |
Correct |
2 ms |
380 KB |
Output is correct |
13 |
Correct |
2 ms |
376 KB |
Output is correct |
14 |
Correct |
2 ms |
504 KB |
Output is correct |
15 |
Correct |
2 ms |
376 KB |
Output is correct |
16 |
Correct |
2 ms |
376 KB |
Output is correct |
17 |
Correct |
2 ms |
504 KB |
Output is correct |
18 |
Correct |
2 ms |
504 KB |
Output is correct |
19 |
Correct |
2 ms |
376 KB |
Output is correct |
20 |
Correct |
2 ms |
376 KB |
Output is correct |
21 |
Correct |
2 ms |
376 KB |
Output is correct |
22 |
Correct |
2 ms |
504 KB |
Output is correct |
23 |
Correct |
2 ms |
376 KB |
Output is correct |
24 |
Correct |
2 ms |
376 KB |
Output is correct |
25 |
Correct |
2 ms |
504 KB |
Output is correct |
26 |
Correct |
2 ms |
376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
504 KB |
Output is correct |
3 |
Correct |
2 ms |
504 KB |
Output is correct |
4 |
Correct |
2 ms |
376 KB |
Output is correct |
5 |
Correct |
2 ms |
376 KB |
Output is correct |
6 |
Correct |
2 ms |
376 KB |
Output is correct |
7 |
Correct |
2 ms |
376 KB |
Output is correct |
8 |
Correct |
2 ms |
504 KB |
Output is correct |
9 |
Correct |
2 ms |
380 KB |
Output is correct |
10 |
Correct |
2 ms |
376 KB |
Output is correct |
11 |
Correct |
2 ms |
376 KB |
Output is correct |
12 |
Correct |
2 ms |
380 KB |
Output is correct |
13 |
Correct |
2 ms |
376 KB |
Output is correct |
14 |
Correct |
2 ms |
504 KB |
Output is correct |
15 |
Correct |
2 ms |
376 KB |
Output is correct |
16 |
Correct |
2 ms |
376 KB |
Output is correct |
17 |
Correct |
2 ms |
504 KB |
Output is correct |
18 |
Correct |
2 ms |
504 KB |
Output is correct |
19 |
Correct |
2 ms |
376 KB |
Output is correct |
20 |
Correct |
2 ms |
376 KB |
Output is correct |
21 |
Correct |
2 ms |
376 KB |
Output is correct |
22 |
Correct |
2 ms |
504 KB |
Output is correct |
23 |
Correct |
2 ms |
376 KB |
Output is correct |
24 |
Correct |
2 ms |
376 KB |
Output is correct |
25 |
Correct |
2 ms |
504 KB |
Output is correct |
26 |
Correct |
2 ms |
376 KB |
Output is correct |
27 |
Correct |
8 ms |
548 KB |
Output is correct |
28 |
Correct |
8 ms |
504 KB |
Output is correct |
29 |
Correct |
8 ms |
376 KB |
Output is correct |
30 |
Correct |
8 ms |
420 KB |
Output is correct |
31 |
Correct |
7 ms |
376 KB |
Output is correct |
32 |
Correct |
10 ms |
376 KB |
Output is correct |
33 |
Correct |
15 ms |
504 KB |
Output is correct |
34 |
Correct |
19 ms |
632 KB |
Output is correct |
35 |
Correct |
17 ms |
376 KB |
Output is correct |
36 |
Correct |
8 ms |
472 KB |
Output is correct |
37 |
Correct |
10 ms |
504 KB |
Output is correct |
38 |
Correct |
10 ms |
504 KB |
Output is correct |
39 |
Correct |
10 ms |
504 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
862 ms |
764 KB |
Output is correct |
2 |
Correct |
877 ms |
936 KB |
Output is correct |
3 |
Correct |
867 ms |
804 KB |
Output is correct |
4 |
Correct |
800 ms |
888 KB |
Output is correct |
5 |
Correct |
506 ms |
760 KB |
Output is correct |
6 |
Correct |
471 ms |
760 KB |
Output is correct |
7 |
Correct |
709 ms |
1020 KB |
Output is correct |
8 |
Correct |
832 ms |
908 KB |
Output is correct |
9 |
Correct |
797 ms |
928 KB |
Output is correct |
10 |
Correct |
822 ms |
896 KB |
Output is correct |
11 |
Correct |
888 ms |
892 KB |
Output is correct |
12 |
Correct |
709 ms |
900 KB |
Output is correct |
13 |
Correct |
600 ms |
920 KB |
Output is correct |
14 |
Correct |
620 ms |
832 KB |
Output is correct |
15 |
Correct |
600 ms |
1032 KB |
Output is correct |
16 |
Correct |
658 ms |
912 KB |
Output is correct |
17 |
Correct |
789 ms |
1016 KB |
Output is correct |
18 |
Correct |
614 ms |
788 KB |
Output is correct |
19 |
Correct |
596 ms |
808 KB |
Output is correct |
20 |
Correct |
708 ms |
1028 KB |
Output is correct |
21 |
Correct |
725 ms |
888 KB |
Output is correct |
22 |
Correct |
692 ms |
916 KB |
Output is correct |
23 |
Correct |
679 ms |
680 KB |
Output is correct |
24 |
Correct |
670 ms |
892 KB |
Output is correct |
25 |
Correct |
696 ms |
892 KB |
Output is correct |
26 |
Correct |
673 ms |
888 KB |
Output is correct |
27 |
Correct |
692 ms |
772 KB |
Output is correct |
28 |
Correct |
923 ms |
1016 KB |
Output is correct |
29 |
Correct |
711 ms |
988 KB |
Output is correct |
30 |
Correct |
738 ms |
896 KB |
Output is correct |
31 |
Correct |
843 ms |
1016 KB |
Output is correct |
32 |
Correct |
975 ms |
892 KB |
Output is correct |
33 |
Correct |
739 ms |
892 KB |
Output is correct |
34 |
Correct |
8 ms |
376 KB |
Output is correct |
35 |
Correct |
8 ms |
376 KB |
Output is correct |
36 |
Correct |
8 ms |
376 KB |
Output is correct |
37 |
Correct |
8 ms |
504 KB |
Output is correct |
38 |
Correct |
7 ms |
532 KB |
Output is correct |
39 |
Correct |
10 ms |
504 KB |
Output is correct |
40 |
Correct |
15 ms |
504 KB |
Output is correct |
41 |
Correct |
19 ms |
480 KB |
Output is correct |
42 |
Correct |
17 ms |
376 KB |
Output is correct |
43 |
Correct |
8 ms |
504 KB |
Output is correct |
44 |
Correct |
10 ms |
508 KB |
Output is correct |
45 |
Correct |
10 ms |
504 KB |
Output is correct |
46 |
Correct |
10 ms |
484 KB |
Output is correct |
47 |
Correct |
2 ms |
504 KB |
Output is correct |
48 |
Correct |
2 ms |
504 KB |
Output is correct |
49 |
Correct |
2 ms |
376 KB |
Output is correct |
50 |
Correct |
2 ms |
376 KB |
Output is correct |
51 |
Correct |
2 ms |
504 KB |
Output is correct |
52 |
Correct |
2 ms |
504 KB |
Output is correct |
53 |
Correct |
2 ms |
376 KB |
Output is correct |
54 |
Correct |
2 ms |
376 KB |
Output is correct |
55 |
Correct |
2 ms |
504 KB |
Output is correct |
56 |
Correct |
2 ms |
376 KB |
Output is correct |
57 |
Correct |
2 ms |
376 KB |
Output is correct |
58 |
Correct |
2 ms |
376 KB |
Output is correct |
59 |
Correct |
2 ms |
504 KB |
Output is correct |
60 |
Correct |
2 ms |
376 KB |
Output is correct |
61 |
Correct |
2 ms |
504 KB |
Output is correct |
62 |
Correct |
2 ms |
504 KB |
Output is correct |
63 |
Correct |
2 ms |
376 KB |
Output is correct |
64 |
Correct |
2 ms |
504 KB |
Output is correct |
65 |
Correct |
2 ms |
504 KB |
Output is correct |
66 |
Correct |
2 ms |
376 KB |
Output is correct |
67 |
Correct |
2 ms |
504 KB |
Output is correct |
68 |
Correct |
2 ms |
504 KB |
Output is correct |
69 |
Correct |
2 ms |
376 KB |
Output is correct |
70 |
Correct |
2 ms |
504 KB |
Output is correct |
71 |
Correct |
2 ms |
376 KB |
Output is correct |
72 |
Correct |
2 ms |
376 KB |
Output is correct |