oj.uz

Submission #436544

# Submission time Handle Problem Language Result Execution time Memory
436544 2021-06-24T15:19:23 Z CodePlatina Keys (IOI21_keys) C++17
100 / 100
 1462 ms 198976 KB 
#include <vector>
#include <algorithm>
#include <tuple>
#include <set>
#include <map>
#define pii pair<int, int>
#define tiii tuple<int, int, int>
#define ff first
#define ss second

using namespace std;

const int INF = (int)1e9 + 7;
vector<int> R, C;
vector<pii> gph[303030];
map<int, int> edge[303030];
map<int, vector<int>> ver[303030];
set<int> key[303030];
vector<pii> ran;
int ord[303030];
int rev[303030];
int cnt = 0;
int val = 0;

int dfs(int x)
{
    int ret = ord[x] = ++cnt;
    rev[cnt] = x;

    vector<int> Q;
    for(auto [y, c] : gph[x])
    {
        if(c == R[x]) Q.push_back(y);
        else if(!ord[y]) ver[x][c].push_back(y);
        else
        {
            if(edge[x].count(c)) edge[x][c] = min(edge[x][c], ord[y]);
            else edge[x][c] = ord[y];
        }
    }
    key[x].insert(R[x]);

    while(Q.size())
    {
        int y = Q.back(); Q.pop_back();
        if(!ord[y])
        {
            int t = dfs(y);
            if(t == -1) return -1;
            ret = min(ret, t);

            if(ver[x].size() + edge[x].size() + key[x].size() < ver[y].size() + edge[y].size() + key[x].size())
            {
                swap(ver[x], ver[y]);
                swap(edge[x], edge[y]);
                swap(key[x], key[y]);
            }

            for(int c : key[y])
            {
                if(ver[x].count(c))
                {
                    for(int z : ver[x][c]) Q.push_back(z);
                    ver[x].erase(c);
                }
                if(edge[x].count(c))
                {
                    ret = min(ret, edge[x][c]);
                    ver[x].erase(c);
                }
                key[x].insert(c);
            }

            for(auto [c, val] : edge[y])
            {
                if(key[x].count(c)) ret = min(ret, val);
                else
                {
                    if(edge[x].count(c)) edge[x][c] = min(edge[x][c], val);
                    else edge[x][c] = val;
                }
            }

            for(auto &[c, v] : ver[y])
            {
                if(key[x].count(c)) for(auto z : v) Q.push_back(z);
                else
                {
                    if(ver[x].count(c))
                    {
                        if(ver[x][c].size() < v.size()) swap(ver[x][c], v);
                        for(auto z : v) ver[x][c].push_back(z);
                    }
                    else ver[x][c] = v;
                }
            }
        }
        else ret = min(ret, ord[y]);
    }

    if(ret < val) { val = ord[x] + 1; return -1; }
    if(ret >= ord[x])
    {
        ran.push_back({ord[x], cnt});
        val = cnt + 1;
        return -1;
    }

    return ret;
}

vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c)
{
    int n = r.size();
    int m = u.size();
    R = r, C = c;

    for(int i = 0; i < m; ++i)
    {
        gph[u[i]].push_back({v[i], c[i]});
        gph[v[i]].push_back({u[i], c[i]});
    }

    for(int i = 0; i < n; ++i) if(!ord[i]) dfs(i);

    int mn = INF;
    for(auto [x, y] : ran) mn = min(mn, y - x);
    vector<int> ans(n);
    for(auto [x, y] : ran) if(mn == y - x)
    {
        for(int i = x; i <= y; ++i)
            ans[rev[i]] = 1;
    }
    return ans;
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 50032 KB Output is correct
2 Correct 34 ms 50044 KB Output is correct
3 Correct 36 ms 50068 KB Output is correct
4 Correct 33 ms 50032 KB Output is correct
5 Correct 35 ms 50080 KB Output is correct
6 Correct 38 ms 50124 KB Output is correct
7 Correct 35 ms 49996 KB Output is correct
8 Correct 35 ms 50116 KB Output is correct
9 Correct 34 ms 50020 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 50032 KB Output is correct
2 Correct 34 ms 50044 KB Output is correct
3 Correct 36 ms 50068 KB Output is correct
4 Correct 33 ms 50032 KB Output is correct
5 Correct 35 ms 50080 KB Output is correct
6 Correct 38 ms 50124 KB Output is correct
7 Correct 35 ms 49996 KB Output is correct
8 Correct 35 ms 50116 KB Output is correct
9 Correct 34 ms 50020 KB Output is correct
10 Correct 34 ms 50124 KB Output is correct
11 Correct 34 ms 50080 KB Output is correct
12 Correct 36 ms 50040 KB Output is correct
13 Correct 35 ms 50084 KB Output is correct
14 Correct 38 ms 49996 KB Output is correct
15 Correct 33 ms 50032 KB Output is correct
16 Correct 32 ms 49996 KB Output is correct
17 Correct 36 ms 49996 KB Output is correct
18 Correct 36 ms 50052 KB Output is correct
19 Correct 34 ms 49996 KB Output is correct
20 Correct 32 ms 50076 KB Output is correct
21 Correct 38 ms 50396 KB Output is correct
22 Correct 42 ms 50092 KB Output is correct
23 Correct 33 ms 50148 KB Output is correct
24 Correct 35 ms 50124 KB Output is correct
25 Correct 34 ms 50160 KB Output is correct
26 Correct 34 ms 50108 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 50032 KB Output is correct
2 Correct 34 ms 50044 KB Output is correct
3 Correct 36 ms 50068 KB Output is correct
4 Correct 33 ms 50032 KB Output is correct
5 Correct 35 ms 50080 KB Output is correct
6 Correct 38 ms 50124 KB Output is correct
7 Correct 35 ms 49996 KB Output is correct
8 Correct 35 ms 50116 KB Output is correct
9 Correct 34 ms 50020 KB Output is correct
10 Correct 34 ms 50124 KB Output is correct
11 Correct 34 ms 50080 KB Output is correct
12 Correct 36 ms 50040 KB Output is correct
13 Correct 35 ms 50084 KB Output is correct
14 Correct 38 ms 49996 KB Output is correct
15 Correct 33 ms 50032 KB Output is correct
16 Correct 32 ms 49996 KB Output is correct
17 Correct 36 ms 49996 KB Output is correct
18 Correct 36 ms 50052 KB Output is correct
19 Correct 34 ms 49996 KB Output is correct
20 Correct 32 ms 50076 KB Output is correct
21 Correct 38 ms 50396 KB Output is correct
22 Correct 42 ms 50092 KB Output is correct
23 Correct 33 ms 50148 KB Output is correct
24 Correct 35 ms 50124 KB Output is correct
25 Correct 34 ms 50160 KB Output is correct
26 Correct 34 ms 50108 KB Output is correct
27 Correct 38 ms 50556 KB Output is correct
28 Correct 35 ms 50508 KB Output is correct
29 Correct 36 ms 50500 KB Output is correct
30 Correct 39 ms 50464 KB Output is correct
31 Correct 38 ms 50252 KB Output is correct
32 Correct 39 ms 50052 KB Output is correct
33 Correct 37 ms 50252 KB Output is correct
34 Correct 58 ms 56372 KB Output is correct
35 Correct 37 ms 50368 KB Output is correct
36 Correct 40 ms 50960 KB Output is correct
37 Correct 41 ms 51020 KB Output is correct
38 Correct 41 ms 51032 KB Output is correct
39 Correct 42 ms 51292 KB Output is correct
40 Correct 35 ms 50292 KB Output is correct
41 Correct 38 ms 50516 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 50032 KB Output is correct
2 Correct 34 ms 50044 KB Output is correct
3 Correct 36 ms 50068 KB Output is correct
4 Correct 33 ms 50032 KB Output is correct
5 Correct 35 ms 50080 KB Output is correct
6 Correct 38 ms 50124 KB Output is correct
7 Correct 35 ms 49996 KB Output is correct
8 Correct 35 ms 50116 KB Output is correct
9 Correct 34 ms 50020 KB Output is correct
10 Correct 624 ms 124072 KB Output is correct
11 Correct 509 ms 91720 KB Output is correct
12 Correct 134 ms 63672 KB Output is correct
13 Correct 550 ms 108748 KB Output is correct
14 Correct 330 ms 196876 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 50032 KB Output is correct
2 Correct 34 ms 50044 KB Output is correct
3 Correct 36 ms 50068 KB Output is correct
4 Correct 33 ms 50032 KB Output is correct
5 Correct 35 ms 50080 KB Output is correct
6 Correct 38 ms 50124 KB Output is correct
7 Correct 35 ms 49996 KB Output is correct
8 Correct 35 ms 50116 KB Output is correct
9 Correct 34 ms 50020 KB Output is correct
10 Correct 34 ms 50124 KB Output is correct
11 Correct 34 ms 50080 KB Output is correct
12 Correct 36 ms 50040 KB Output is correct
13 Correct 35 ms 50084 KB Output is correct
14 Correct 38 ms 49996 KB Output is correct
15 Correct 33 ms 50032 KB Output is correct
16 Correct 32 ms 49996 KB Output is correct
17 Correct 36 ms 49996 KB Output is correct
18 Correct 36 ms 50052 KB Output is correct
19 Correct 34 ms 49996 KB Output is correct
20 Correct 32 ms 50076 KB Output is correct
21 Correct 38 ms 50396 KB Output is correct
22 Correct 42 ms 50092 KB Output is correct
23 Correct 33 ms 50148 KB Output is correct
24 Correct 35 ms 50124 KB Output is correct
25 Correct 34 ms 50160 KB Output is correct
26 Correct 34 ms 50108 KB Output is correct
27 Correct 38 ms 50556 KB Output is correct
28 Correct 35 ms 50508 KB Output is correct
29 Correct 36 ms 50500 KB Output is correct
30 Correct 39 ms 50464 KB Output is correct
31 Correct 38 ms 50252 KB Output is correct
32 Correct 39 ms 50052 KB Output is correct
33 Correct 37 ms 50252 KB Output is correct
34 Correct 58 ms 56372 KB Output is correct
35 Correct 37 ms 50368 KB Output is correct
36 Correct 40 ms 50960 KB Output is correct
37 Correct 41 ms 51020 KB Output is correct
38 Correct 41 ms 51032 KB Output is correct
39 Correct 42 ms 51292 KB Output is correct
40 Correct 35 ms 50292 KB Output is correct
41 Correct 38 ms 50516 KB Output is correct
42 Correct 624 ms 124072 KB Output is correct
43 Correct 509 ms 91720 KB Output is correct
44 Correct 134 ms 63672 KB Output is correct
45 Correct 550 ms 108748 KB Output is correct
46 Correct 330 ms 196876 KB Output is correct
47 Correct 33 ms 49996 KB Output is correct
48 Correct 33 ms 50104 KB Output is correct
49 Correct 33 ms 50080 KB Output is correct
50 Correct 298 ms 144500 KB Output is correct
51 Correct 293 ms 143628 KB Output is correct
52 Correct 423 ms 101800 KB Output is correct
53 Correct 379 ms 101864 KB Output is correct
54 Correct 416 ms 101928 KB Output is correct
55 Correct 701 ms 139496 KB Output is correct
56 Correct 625 ms 128436 KB Output is correct
57 Correct 383 ms 124080 KB Output is correct
58 Correct 707 ms 124216 KB Output is correct
59 Correct 1407 ms 168836 KB Output is correct
60 Correct 671 ms 129236 KB Output is correct
61 Correct 1187 ms 193416 KB Output is correct
62 Correct 1010 ms 170896 KB Output is correct
63 Correct 328 ms 113652 KB Output is correct
64 Correct 47 ms 53456 KB Output is correct
65 Correct 57 ms 54548 KB Output is correct
66 Correct 1025 ms 170964 KB Output is correct
67 Correct 79 ms 66884 KB Output is correct
68 Correct 107 ms 76596 KB Output is correct
69 Correct 1441 ms 169148 KB Output is correct
70 Correct 147 ms 101136 KB Output is correct
71 Correct 341 ms 198976 KB Output is correct
72 Correct 1462 ms 168996 KB Output is correct
73 Correct 1029 ms 170960 KB Output is correct