| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 434994 |
2021-06-22T18:10:50 Z |
grt |
Keys (IOI21_keys) |
C++17 |
|
32 ms |
42572 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 = 300 * 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);
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] = true;
for(int i = 0; i <= ver; ++i) {
for(int nbh : G[i]) {
if(SCC[nbh] != SCC[i]) {
ok[SCC[i]] = false;
}
}
}
int mi = INF;
for(int i = 1; i <= color; ++i) {
if(!ok[i]) continue;
mi = min(mi, cnt[i]);
}
vector<int>ans(n);
for(int i = 0; i < n; ++i) {
if(cnt[SCC[i]] == mi) {
ans[i] = true;
} else {
ans[i] = false;
}
}
return ans;
}
//int main() {
//ios_base::sync_with_stdio(0);
//cin.tie(0);
//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 << " ";
//}
//}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
32 ms |
42572 KB |
Output is correct |
| 2 |
Incorrect |
31 ms |
42552 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
32 ms |
42572 KB |
Output is correct |
| 2 |
Incorrect |
31 ms |
42552 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
32 ms |
42572 KB |
Output is correct |
| 2 |
Incorrect |
31 ms |
42552 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
32 ms |
42572 KB |
Output is correct |
| 2 |
Incorrect |
31 ms |
42552 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
32 ms |
42572 KB |
Output is correct |
| 2 |
Incorrect |
31 ms |
42552 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
