oj.uz

Submission #469120

# Submission time Handle Problem Language Result Execution time Memory
469120 2021-08-30T20:03:54 Z kevinxiehk Keys (IOI21_keys) C++17
9 / 100
 357 ms 91488 KB 
#include <bits/stdc++.h>
#define mp make_pair
#define pb emplace_back
#define fi first
#define se second
using namespace std;
set<int> conn[300005];
set<int> conn2[300005];
stack<int> rec;
pair<int, int> val[300005];
bool instack[300005];
int scc[300005];
int sz[300005];
vector<int> component[300005];
int cnt = 0;
int n, m, t, tt, k = 1;
void dfs(int now) {
    val[now] = mp(k, k);
    k++;
    rec.push(now);
    instack[now] = true;
    for(auto x: conn[now]) {
        if(val[x].fi == 0) {
            dfs(x);
        }
        if(instack[x]) {
            val[now].se = min(val[now].se, val[x].se);
        }
    }
    if(val[now].se == val[now].fi) {
        cnt++;
        while(rec.top() != now) {
            instack[rec.top()] = false;
            scc[rec.top()] = cnt;
            component[cnt].pb(rec.top());
            rec.pop();
        }
        instack[rec.top()] = false;
        scc[rec.top()] = cnt;
        component[cnt].pb(rec.top());
        rec.pop();
    }
}
vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c) {
    n = r.size();
    m = u.size();
    for(int i = 0; i < m; i++) {
        if(r[u[i]] == c[i]) conn[u[i]].insert(v[i]);
        if(r[v[i]] == c[i]) conn[v[i]].insert(u[i]);
    }
    for(int i = 0; i < n; i++) if(val[i].fi == 0) dfs(i);
    for(int i = 0; i < n; i++) {
        for(auto x: conn[i]) {
            if(scc[i] != scc[x]) conn2[scc[i]].insert(scc[x]);
        }
    }
    int mi = n + 5;
    for(int i = 1; i <= cnt; i++) if(conn2[i].size() == 0) mi = min(mi, (int)(component[i].size()));
	vector<int> ans(r.size(), 0);
    for(int i = 1; i <= cnt; i++) {
        if(conn2[i].size() == 0 && component[i].size() == mi) {
            for(auto x: component[i]) ans[x] = true;
        }
    }
	return ans;
}

Compilation message

keys.cpp: In function 'std::vector<int> find_reachable(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
keys.cpp:61:56: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   61 |         if(conn2[i].size() == 0 && component[i].size() == mi) {
      |                                    ~~~~~~~~~~~~~~~~~~~~^~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 35524 KB Output is correct
2 Correct 20 ms 35532 KB Output is correct
3 Correct 19 ms 35540 KB Output is correct
4 Correct 20 ms 35580 KB Output is correct
5 Correct 21 ms 35436 KB Output is correct
6 Correct 20 ms 35456 KB Output is correct
7 Correct 20 ms 35480 KB Output is correct
8 Correct 19 ms 35576 KB Output is correct
9 Correct 19 ms 35532 KB Output is correct

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 35524 KB Output is correct
2 Correct 20 ms 35532 KB Output is correct
3 Correct 19 ms 35540 KB Output is correct
4 Correct 20 ms 35580 KB Output is correct
5 Correct 21 ms 35436 KB Output is correct
6 Correct 20 ms 35456 KB Output is correct
7 Correct 20 ms 35480 KB Output is correct
8 Correct 19 ms 35576 KB Output is correct
9 Correct 19 ms 35532 KB Output is correct
10 Correct 19 ms 35532 KB Output is correct
11 Correct 22 ms 35536 KB Output is correct
12 Correct 19 ms 35524 KB Output is correct
13 Correct 21 ms 35564 KB Output is correct
14 Correct 20 ms 35512 KB Output is correct
15 Correct 20 ms 35456 KB Output is correct
16 Correct 19 ms 35532 KB Output is correct
17 Incorrect 20 ms 35532 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 35524 KB Output is correct
2 Correct 20 ms 35532 KB Output is correct
3 Correct 19 ms 35540 KB Output is correct
4 Correct 20 ms 35580 KB Output is correct
5 Correct 21 ms 35436 KB Output is correct
6 Correct 20 ms 35456 KB Output is correct
7 Correct 20 ms 35480 KB Output is correct
8 Correct 19 ms 35576 KB Output is correct
9 Correct 19 ms 35532 KB Output is correct
10 Correct 19 ms 35532 KB Output is correct
11 Correct 22 ms 35536 KB Output is correct
12 Correct 19 ms 35524 KB Output is correct
13 Correct 21 ms 35564 KB Output is correct
14 Correct 20 ms 35512 KB Output is correct
15 Correct 20 ms 35456 KB Output is correct
16 Correct 19 ms 35532 KB Output is correct
17 Incorrect 20 ms 35532 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 35524 KB Output is correct
2 Correct 20 ms 35532 KB Output is correct
3 Correct 19 ms 35540 KB Output is correct
4 Correct 20 ms 35580 KB Output is correct
5 Correct 21 ms 35436 KB Output is correct
6 Correct 20 ms 35456 KB Output is correct
7 Correct 20 ms 35480 KB Output is correct
8 Correct 19 ms 35576 KB Output is correct
9 Correct 19 ms 35532 KB Output is correct
10 Correct 212 ms 63096 KB Output is correct
11 Incorrect 357 ms 91488 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 35524 KB Output is correct
2 Correct 20 ms 35532 KB Output is correct
3 Correct 19 ms 35540 KB Output is correct
4 Correct 20 ms 35580 KB Output is correct
5 Correct 21 ms 35436 KB Output is correct
6 Correct 20 ms 35456 KB Output is correct
7 Correct 20 ms 35480 KB Output is correct
8 Correct 19 ms 35576 KB Output is correct
9 Correct 19 ms 35532 KB Output is correct
10 Correct 19 ms 35532 KB Output is correct
11 Correct 22 ms 35536 KB Output is correct
12 Correct 19 ms 35524 KB Output is correct
13 Correct 21 ms 35564 KB Output is correct
14 Correct 20 ms 35512 KB Output is correct
15 Correct 20 ms 35456 KB Output is correct
16 Correct 19 ms 35532 KB Output is correct
17 Incorrect 20 ms 35532 KB Output isn't correct
18 Halted 0 ms 0 KB -