# |
제출 시각 |
아이디 |
문제 |
언어 |
결과 |
실행 시간 |
메모리 |
435000 |
2021-06-22T18:44:06 Z |
grt |
열쇠 (IOI21_keys) |
C++17 |
|
1610 ms |
160420 KB |
#include <bits/stdc++.h>
#define ST first
#define ND second
#define PB push_back
using namespace std;
using ll = long long;
using pi = pair<int,int>;
using vi = vector<int>;
const int nax = 600 * 1000 + 10, INF = 1e9;
int n, m, nr;
map<int, vi>V[nax];
bool vis[2 * nax];
vi seen;
vi G[2 * nax];
vi Grev[2 * nax];
int topo[2 * nax];
int SCC[2 * nax];
bool ok[2 * nax];
int color;
int cnt[2 * nax];
void dfs(int x, int col) {
vis[x] = true;
seen.PB(x);
for(auto ed : V[col][x]) if(!vis[ed]) {
dfs(ed, col);
}
}
void dfs2(int x) {
vis[x] = true;
for(int nbh : G[x]) {
if(!vis[nbh]) {
dfs2(nbh);
}
}
topo[nr++] = x;
}
void dfs3(int x) {
vis[x] = true;
SCC[x] = color;
if(x < n) cnt[color]++;
for(int nbh : Grev[x]) if(!vis[nbh]) {
dfs3(nbh);
}
}
vi find_reachable(vi r, vi u, vi v, vi c) {
n = (int)r.size();
m = (int)u.size();
for(int i = 0; i < m; ++i) {
V[c[i]][u[i]].PB(v[i]);
V[c[i]][v[i]].PB(u[i]);
}
int ver = n-1;
for(int i = 0; i < n; ++i) {
for(auto it : V[i]) {
if(!vis[it.ST]) {
seen.clear();
dfs(it.ST, i);
bool any = false;
for(auto x : seen) {
if(r[x] == i) any = true;
}
if(!any) continue;
ver++;
for(auto x : seen) {
G[ver].PB(x);
Grev[x].PB(ver);
if(r[x] == i) {
G[x].PB(ver);
Grev[ver].PB(x);
}
}
}
}
for(auto it : V[i]) vis[it.ST] = false;
}
for(int i = 0; i <= ver; ++i) {
if(!vis[i]) {
dfs2(i);
}
}
for(int i = 0; i <= ver; ++i) {
vis[i] = false;
}
for(int i = ver; i >= 0; --i) {
if(!vis[topo[i]]) {
color++;
dfs3(topo[i]);
}
}
for(int i = 0; i <= ver; ++i) ok[i] = false;
for(int i = 0; i < n; ++i) ok[SCC[i]] = true;
for(int i = 0; i <= ver; ++i) {
//cout << SCC[i] << " ";
for(int nbh : G[i]) {
if(SCC[nbh] != SCC[i]) {
ok[SCC[i]] = false;
}
}
}
//cout << "\n";
int mi = INF;
for(int i = 1; i <= color; ++i) {
//cout << cnt[i] << " ";
if(!ok[i]) continue;
mi = min(mi, cnt[i]);
}
//cout << "\n";
vector<int>ans(n);
for(int i = 0; i < n; ++i) {
if(ok[SCC[i]] && cnt[SCC[i]] == mi) {
ans[i] = true;
} else {
ans[i] = false;
}
}
return ans;
}
//int main() {
//ios_base::sync_with_stdio(0);
//cin.tie(0);
//int N, M;
//cin >> N >> M;
//vi r(N), u(M), v(M), c(M);
//for(int i = 0; i < N; ++i) {
//cin >> r[i];
//}
//for(int i = 0; i < M; ++i) {
//cin >> u[i] >> v[i] >> c[i];
//}
//vi w = find_reachable(r,u,v,c);
//vi w = find_reachable({0, 1, 1, 2},{0, 0, 1, 1, 3}, {1, 2, 2, 3, 1}, {0, 0, 1, 0, 2});
//vi w = find_reachable({0, 1, 1, 2, 2, 1, 2},{0, 0, 1, 1, 2, 3, 3, 4, 4, 5},
//{1, 2, 2, 3, 3, 4, 5, 5, 6, 6},
//{0, 0, 1, 0, 0, 1, 2, 0, 2, 1});
//vi w = find_reachable({0, 0, 0}, {0}, {1}, {0});
//for(int x : w) {
//cout << x << " ";
//}
//}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
60 ms |
84816 KB |
Output is correct |
2 |
Correct |
57 ms |
84756 KB |
Output is correct |
3 |
Correct |
67 ms |
84748 KB |
Output is correct |
4 |
Correct |
58 ms |
84804 KB |
Output is correct |
5 |
Correct |
57 ms |
84832 KB |
Output is correct |
6 |
Correct |
59 ms |
84840 KB |
Output is correct |
7 |
Correct |
62 ms |
84856 KB |
Output is correct |
8 |
Correct |
61 ms |
84880 KB |
Output is correct |
9 |
Correct |
58 ms |
84780 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
60 ms |
84816 KB |
Output is correct |
2 |
Correct |
57 ms |
84756 KB |
Output is correct |
3 |
Correct |
67 ms |
84748 KB |
Output is correct |
4 |
Correct |
58 ms |
84804 KB |
Output is correct |
5 |
Correct |
57 ms |
84832 KB |
Output is correct |
6 |
Correct |
59 ms |
84840 KB |
Output is correct |
7 |
Correct |
62 ms |
84856 KB |
Output is correct |
8 |
Correct |
61 ms |
84880 KB |
Output is correct |
9 |
Correct |
58 ms |
84780 KB |
Output is correct |
10 |
Correct |
58 ms |
84844 KB |
Output is correct |
11 |
Correct |
62 ms |
84916 KB |
Output is correct |
12 |
Correct |
64 ms |
84904 KB |
Output is correct |
13 |
Correct |
64 ms |
84812 KB |
Output is correct |
14 |
Correct |
71 ms |
84828 KB |
Output is correct |
15 |
Correct |
59 ms |
84816 KB |
Output is correct |
16 |
Correct |
68 ms |
84760 KB |
Output is correct |
17 |
Correct |
59 ms |
84784 KB |
Output is correct |
18 |
Correct |
59 ms |
84804 KB |
Output is correct |
19 |
Correct |
61 ms |
84844 KB |
Output is correct |
20 |
Correct |
64 ms |
84784 KB |
Output is correct |
21 |
Correct |
59 ms |
84804 KB |
Output is correct |
22 |
Correct |
58 ms |
84804 KB |
Output is correct |
23 |
Correct |
59 ms |
84804 KB |
Output is correct |
24 |
Correct |
58 ms |
84804 KB |
Output is correct |
25 |
Correct |
59 ms |
84940 KB |
Output is correct |
26 |
Correct |
62 ms |
84852 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
60 ms |
84816 KB |
Output is correct |
2 |
Correct |
57 ms |
84756 KB |
Output is correct |
3 |
Correct |
67 ms |
84748 KB |
Output is correct |
4 |
Correct |
58 ms |
84804 KB |
Output is correct |
5 |
Correct |
57 ms |
84832 KB |
Output is correct |
6 |
Correct |
59 ms |
84840 KB |
Output is correct |
7 |
Correct |
62 ms |
84856 KB |
Output is correct |
8 |
Correct |
61 ms |
84880 KB |
Output is correct |
9 |
Correct |
58 ms |
84780 KB |
Output is correct |
10 |
Correct |
58 ms |
84844 KB |
Output is correct |
11 |
Correct |
62 ms |
84916 KB |
Output is correct |
12 |
Correct |
64 ms |
84904 KB |
Output is correct |
13 |
Correct |
64 ms |
84812 KB |
Output is correct |
14 |
Correct |
71 ms |
84828 KB |
Output is correct |
15 |
Correct |
59 ms |
84816 KB |
Output is correct |
16 |
Correct |
68 ms |
84760 KB |
Output is correct |
17 |
Correct |
59 ms |
84784 KB |
Output is correct |
18 |
Correct |
59 ms |
84804 KB |
Output is correct |
19 |
Correct |
61 ms |
84844 KB |
Output is correct |
20 |
Correct |
64 ms |
84784 KB |
Output is correct |
21 |
Correct |
59 ms |
84804 KB |
Output is correct |
22 |
Correct |
58 ms |
84804 KB |
Output is correct |
23 |
Correct |
59 ms |
84804 KB |
Output is correct |
24 |
Correct |
58 ms |
84804 KB |
Output is correct |
25 |
Correct |
59 ms |
84940 KB |
Output is correct |
26 |
Correct |
62 ms |
84852 KB |
Output is correct |
27 |
Correct |
60 ms |
85544 KB |
Output is correct |
28 |
Correct |
62 ms |
85444 KB |
Output is correct |
29 |
Correct |
60 ms |
85488 KB |
Output is correct |
30 |
Correct |
65 ms |
85280 KB |
Output is correct |
31 |
Correct |
64 ms |
85004 KB |
Output is correct |
32 |
Incorrect |
62 ms |
84932 KB |
Output isn't correct |
33 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
60 ms |
84816 KB |
Output is correct |
2 |
Correct |
57 ms |
84756 KB |
Output is correct |
3 |
Correct |
67 ms |
84748 KB |
Output is correct |
4 |
Correct |
58 ms |
84804 KB |
Output is correct |
5 |
Correct |
57 ms |
84832 KB |
Output is correct |
6 |
Correct |
59 ms |
84840 KB |
Output is correct |
7 |
Correct |
62 ms |
84856 KB |
Output is correct |
8 |
Correct |
61 ms |
84880 KB |
Output is correct |
9 |
Correct |
58 ms |
84780 KB |
Output is correct |
10 |
Correct |
1610 ms |
160420 KB |
Output is correct |
11 |
Incorrect |
1227 ms |
153948 KB |
Output isn't correct |
12 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
60 ms |
84816 KB |
Output is correct |
2 |
Correct |
57 ms |
84756 KB |
Output is correct |
3 |
Correct |
67 ms |
84748 KB |
Output is correct |
4 |
Correct |
58 ms |
84804 KB |
Output is correct |
5 |
Correct |
57 ms |
84832 KB |
Output is correct |
6 |
Correct |
59 ms |
84840 KB |
Output is correct |
7 |
Correct |
62 ms |
84856 KB |
Output is correct |
8 |
Correct |
61 ms |
84880 KB |
Output is correct |
9 |
Correct |
58 ms |
84780 KB |
Output is correct |
10 |
Correct |
58 ms |
84844 KB |
Output is correct |
11 |
Correct |
62 ms |
84916 KB |
Output is correct |
12 |
Correct |
64 ms |
84904 KB |
Output is correct |
13 |
Correct |
64 ms |
84812 KB |
Output is correct |
14 |
Correct |
71 ms |
84828 KB |
Output is correct |
15 |
Correct |
59 ms |
84816 KB |
Output is correct |
16 |
Correct |
68 ms |
84760 KB |
Output is correct |
17 |
Correct |
59 ms |
84784 KB |
Output is correct |
18 |
Correct |
59 ms |
84804 KB |
Output is correct |
19 |
Correct |
61 ms |
84844 KB |
Output is correct |
20 |
Correct |
64 ms |
84784 KB |
Output is correct |
21 |
Correct |
59 ms |
84804 KB |
Output is correct |
22 |
Correct |
58 ms |
84804 KB |
Output is correct |
23 |
Correct |
59 ms |
84804 KB |
Output is correct |
24 |
Correct |
58 ms |
84804 KB |
Output is correct |
25 |
Correct |
59 ms |
84940 KB |
Output is correct |
26 |
Correct |
62 ms |
84852 KB |
Output is correct |
27 |
Correct |
60 ms |
85544 KB |
Output is correct |
28 |
Correct |
62 ms |
85444 KB |
Output is correct |
29 |
Correct |
60 ms |
85488 KB |
Output is correct |
30 |
Correct |
65 ms |
85280 KB |
Output is correct |
31 |
Correct |
64 ms |
85004 KB |
Output is correct |
32 |
Incorrect |
62 ms |
84932 KB |
Output isn't correct |
33 |
Halted |
0 ms |
0 KB |
- |