oj.uz

Submission #436542

# Submission time Handle Problem Language Result Execution time Memory
436542 2021-06-24T15:17:50 Z CodePlatina Keys (IOI21_keys) C++17
100 / 100
 1359 ms 198864 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;

//namespace A{

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();
//    init();
    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;
}

//}
//
//namespace B{
//
//    vector<pii> gph[303030];
//
//    void init(int n)
//    {
//        for(int i = 0; i < n; ++i) gph[i].clear();
//    }
//
//    vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c)
//    {
//        int n = r.size();
//        int m = u.size();
//        init(n);
//        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]});
//        }
//
//        int cnt[n]{};
//        int mn = n;
//        for(int x = 0; x < n; ++x)
//        {
//            bool vst[n]{};
//            bool col[n]{};
//            vector<int> Q;
//            vector<int> ls[n];
//            Q.push_back(x);
//            while(Q.size())
//            {
//                int i = Q.back(); Q.pop_back();
//                if(vst[i]) continue;
//                vst[i] = true;
//                if(!col[r[i]])
//                {
//                    for(auto j : ls[r[i]]) Q.push_back(j);
//                    col[r[i]] = true;
//                }
//                for(auto [j, e] : gph[i])
//                {
//                    if(col[e]) Q.push_back(j);
//                    else ls[e].push_back(j);
//                }
//            }
//            for(int i = 0; i < n; ++i) if(vst[i]) ++cnt[x];
//            mn = min(mn, cnt[x]);
//        }
//
//        vector<int> ans(n);
//        for(int i = 0; i < n; ++i) if(cnt[i] == mn) ans[i] = 1;
//        return ans;
//    }
//}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 50080 KB Output is correct
2 Correct 36 ms 50020 KB Output is correct
3 Correct 37 ms 50072 KB Output is correct
4 Correct 38 ms 50132 KB Output is correct
5 Correct 36 ms 49988 KB Output is correct
6 Correct 36 ms 50028 KB Output is correct
7 Correct 34 ms 49996 KB Output is correct
8 Correct 37 ms 50116 KB Output is correct
9 Correct 36 ms 50152 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 50080 KB Output is correct
2 Correct 36 ms 50020 KB Output is correct
3 Correct 37 ms 50072 KB Output is correct
4 Correct 38 ms 50132 KB Output is correct
5 Correct 36 ms 49988 KB Output is correct
6 Correct 36 ms 50028 KB Output is correct
7 Correct 34 ms 49996 KB Output is correct
8 Correct 37 ms 50116 KB Output is correct
9 Correct 36 ms 50152 KB Output is correct
10 Correct 32 ms 50080 KB Output is correct
11 Correct 36 ms 50080 KB Output is correct
12 Correct 35 ms 50132 KB Output is correct
13 Correct 36 ms 49988 KB Output is correct
14 Correct 35 ms 50132 KB Output is correct
15 Correct 34 ms 50124 KB Output is correct
16 Correct 36 ms 50092 KB Output is correct
17 Correct 34 ms 50100 KB Output is correct
18 Correct 38 ms 50076 KB Output is correct
19 Correct 33 ms 50092 KB Output is correct
20 Correct 33 ms 50056 KB Output is correct
21 Correct 36 ms 50432 KB Output is correct
22 Correct 38 ms 50032 KB Output is correct
23 Correct 35 ms 50124 KB Output is correct
24 Correct 38 ms 50084 KB Output is correct
25 Correct 33 ms 50124 KB Output is correct
26 Correct 34 ms 50156 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 50080 KB Output is correct
2 Correct 36 ms 50020 KB Output is correct
3 Correct 37 ms 50072 KB Output is correct
4 Correct 38 ms 50132 KB Output is correct
5 Correct 36 ms 49988 KB Output is correct
6 Correct 36 ms 50028 KB Output is correct
7 Correct 34 ms 49996 KB Output is correct
8 Correct 37 ms 50116 KB Output is correct
9 Correct 36 ms 50152 KB Output is correct
10 Correct 32 ms 50080 KB Output is correct
11 Correct 36 ms 50080 KB Output is correct
12 Correct 35 ms 50132 KB Output is correct
13 Correct 36 ms 49988 KB Output is correct
14 Correct 35 ms 50132 KB Output is correct
15 Correct 34 ms 50124 KB Output is correct
16 Correct 36 ms 50092 KB Output is correct
17 Correct 34 ms 50100 KB Output is correct
18 Correct 38 ms 50076 KB Output is correct
19 Correct 33 ms 50092 KB Output is correct
20 Correct 33 ms 50056 KB Output is correct
21 Correct 36 ms 50432 KB Output is correct
22 Correct 38 ms 50032 KB Output is correct
23 Correct 35 ms 50124 KB Output is correct
24 Correct 38 ms 50084 KB Output is correct
25 Correct 33 ms 50124 KB Output is correct
26 Correct 34 ms 50156 KB Output is correct
27 Correct 37 ms 50520 KB Output is correct
28 Correct 38 ms 50500 KB Output is correct
29 Correct 40 ms 50648 KB Output is correct
30 Correct 41 ms 50628 KB Output is correct
31 Correct 35 ms 50252 KB Output is correct
32 Correct 34 ms 50164 KB Output is correct
33 Correct 35 ms 50252 KB Output is correct
34 Correct 55 ms 56416 KB Output is correct
35 Correct 39 ms 50388 KB Output is correct
36 Correct 42 ms 51000 KB Output is correct
37 Correct 39 ms 51028 KB Output is correct
38 Correct 39 ms 51020 KB Output is correct
39 Correct 38 ms 51288 KB Output is correct
40 Correct 36 ms 50292 KB Output is correct
41 Correct 36 ms 50476 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 50080 KB Output is correct
2 Correct 36 ms 50020 KB Output is correct
3 Correct 37 ms 50072 KB Output is correct
4 Correct 38 ms 50132 KB Output is correct
5 Correct 36 ms 49988 KB Output is correct
6 Correct 36 ms 50028 KB Output is correct
7 Correct 34 ms 49996 KB Output is correct
8 Correct 37 ms 50116 KB Output is correct
9 Correct 36 ms 50152 KB Output is correct
10 Correct 610 ms 124060 KB Output is correct
11 Correct 477 ms 91628 KB Output is correct
12 Correct 158 ms 63664 KB Output is correct
13 Correct 552 ms 108900 KB Output is correct
14 Correct 378 ms 196932 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 50080 KB Output is correct
2 Correct 36 ms 50020 KB Output is correct
3 Correct 37 ms 50072 KB Output is correct
4 Correct 38 ms 50132 KB Output is correct
5 Correct 36 ms 49988 KB Output is correct
6 Correct 36 ms 50028 KB Output is correct
7 Correct 34 ms 49996 KB Output is correct
8 Correct 37 ms 50116 KB Output is correct
9 Correct 36 ms 50152 KB Output is correct
10 Correct 32 ms 50080 KB Output is correct
11 Correct 36 ms 50080 KB Output is correct
12 Correct 35 ms 50132 KB Output is correct
13 Correct 36 ms 49988 KB Output is correct
14 Correct 35 ms 50132 KB Output is correct
15 Correct 34 ms 50124 KB Output is correct
16 Correct 36 ms 50092 KB Output is correct
17 Correct 34 ms 50100 KB Output is correct
18 Correct 38 ms 50076 KB Output is correct
19 Correct 33 ms 50092 KB Output is correct
20 Correct 33 ms 50056 KB Output is correct
21 Correct 36 ms 50432 KB Output is correct
22 Correct 38 ms 50032 KB Output is correct
23 Correct 35 ms 50124 KB Output is correct
24 Correct 38 ms 50084 KB Output is correct
25 Correct 33 ms 50124 KB Output is correct
26 Correct 34 ms 50156 KB Output is correct
27 Correct 37 ms 50520 KB Output is correct
28 Correct 38 ms 50500 KB Output is correct
29 Correct 40 ms 50648 KB Output is correct
30 Correct 41 ms 50628 KB Output is correct
31 Correct 35 ms 50252 KB Output is correct
32 Correct 34 ms 50164 KB Output is correct
33 Correct 35 ms 50252 KB Output is correct
34 Correct 55 ms 56416 KB Output is correct
35 Correct 39 ms 50388 KB Output is correct
36 Correct 42 ms 51000 KB Output is correct
37 Correct 39 ms 51028 KB Output is correct
38 Correct 39 ms 51020 KB Output is correct
39 Correct 38 ms 51288 KB Output is correct
40 Correct 36 ms 50292 KB Output is correct
41 Correct 36 ms 50476 KB Output is correct
42 Correct 610 ms 124060 KB Output is correct
43 Correct 477 ms 91628 KB Output is correct
44 Correct 158 ms 63664 KB Output is correct
45 Correct 552 ms 108900 KB Output is correct
46 Correct 378 ms 196932 KB Output is correct
47 Correct 34 ms 50080 KB Output is correct
48 Correct 35 ms 50116 KB Output is correct
49 Correct 33 ms 50104 KB Output is correct
50 Correct 290 ms 144492 KB Output is correct
51 Correct 360 ms 143672 KB Output is correct
52 Correct 375 ms 101820 KB Output is correct
53 Correct 436 ms 101816 KB Output is correct
54 Correct 416 ms 101860 KB Output is correct
55 Correct 743 ms 139488 KB Output is correct
56 Correct 645 ms 128496 KB Output is correct
57 Correct 391 ms 124048 KB Output is correct
58 Correct 682 ms 124096 KB Output is correct
59 Correct 1345 ms 168856 KB Output is correct
60 Correct 693 ms 129288 KB Output is correct
61 Correct 1130 ms 193428 KB Output is correct
62 Correct 999 ms 171076 KB Output is correct
63 Correct 385 ms 113668 KB Output is correct
64 Correct 41 ms 53424 KB Output is correct
65 Correct 46 ms 54476 KB Output is correct
66 Correct 1029 ms 170900 KB Output is correct
67 Correct 74 ms 66884 KB Output is correct
68 Correct 101 ms 76612 KB Output is correct
69 Correct 1253 ms 169024 KB Output is correct
70 Correct 136 ms 101112 KB Output is correct
71 Correct 349 ms 198864 KB Output is correct
72 Correct 1359 ms 169060 KB Output is correct
73 Correct 1060 ms 170868 KB Output is correct