oj.uz

Submission #491361

# Submission time Handle Problem Language Result Execution time Memory
491361 2021-12-01T17:30:03 Z qwerasdfzxcl Simurgh (IOI17_simurgh) C++14
100 / 100
 555 ms 7204 KB 
#include "simurgh.h"
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int INF = 1e9;
struct DSU{
    int path[505];
    void init(int n){for (int i=0;i<=n;i++) path[i] = i;}
    int find(int s){
        if (path[s]==s) return s;
        return path[s] = find(path[s]);
    }
    bool merge(int s, int v){
        int x = find(s), y = find(v);
        if (x==y) return 0;
        path[x] = y;
        return 1;
    }
}dsu;
int adj[505][505], n, val[250250], dfs_chk[250250], cntq;
bool visited[505];
vector<int> U, V, DV, E, F, adj2[505];

void dfs(int s){
    visited[s] = 1;
    for (int i=0;i<n;i++) if (!visited[i] && adj[s][i]!=-1){
        DV.push_back(adj[s][i]);
        dfs_chk[adj[s][i]] = 1;
        adj2[s].push_back(i);
        adj2[i].push_back(s);
        dfs(i);
    }
}

bool find_path(int s, int e){
    if (s==e) return 1;
    visited[s] = 1;
    for (auto &v:adj2[s]) if (!visited[v]){
        E.push_back(adj[s][v]);
        if (find_path(v, e)) return 1;
        E.pop_back();
    }
    return 0;
}

int calc(int p, int l, int r){
    if (l>r) return 0;
    //printf("calc: %d %d %d\n", p, l, r);
    dsu.init(n);
    vector<int> Q;
    for (int i=l;i<=r;i++) if (adj[p][i]!=-1){
        Q.push_back(adj[p][i]);
        dsu.merge(p, i);
    }

    int cnt = 0;
    for (auto &t:DV) if (dsu.merge(U[t], V[t])){
        Q.push_back(t);
        if (val[t]==1) cnt++;
    }
    cntq++;
    assert(cntq<=n*12);

    return count_common_roads(Q) - cnt;
}

std::vector<int> find_roads(int N, std::vector<int> u, std::vector<int> v) {
    cntq = 0;
    if (N==2) return {0};
    n = N;
    U = u, V = v;
    fill(adj[0], adj[504]+505, -1);
    for (int i=0;i<(int)u.size();i++){
        adj[u[i]][v[i]] = i;
        adj[v[i]][u[i]] = i;
    }

    fill(val, val+250250, -1);
    fill(dfs_chk, dfs_chk+250250, 0);
    fill(visited, visited+505, 0);
    DV.clear();
    for (int i=0;i<505;i++) adj2[i].clear();
    dfs(0);
    int cnt0 = count_common_roads(DV);
    //for (auto &x:DV) printf("%d ", x);
    //printf("\n");
    cntq++;

    for (int i=0;i<(int)u.size();i++) if (!dfs_chk[i]){
        E.clear();
        F.clear();
        fill(visited, visited+n, 0);
        assert(find_path(u[i], v[i]));
        //printf("%d: ", i);
        //for (auto &x:E) printf("%d ", x);
        //printf("\n");

        bool flag = 0, flag2 = 0;;
        for (auto &t:E) if (val[t]!=-1) flag = 1;
        for (auto &t:E) if (val[t]==-1) flag2 = 1;
        if (!flag2) continue;

        vector<int> Q = DV;
        int flag3 = -1, val2 = -1;
        int prvE = i;
        for (auto &t:E){
            if (flag3!=-1 && val[t]!=-1) {F.push_back(INF); continue;}
            for (auto iter = Q.begin();iter!=Q.end();iter++) if (*iter==t) {Q.erase(iter); break;}
            Q.push_back(prvE);
            F.push_back(count_common_roads(Q));
            cntq++;
            assert(cntq<=n*12);
            prvE = t;

            if (val[t]!=-1) flag3 = t, val2 = F.back();
        }

        if (!flag){
            int mn = min(*min_element(F.begin(), F.end()), cnt0);
            int mx = max(*max_element(F.begin(), F.end()), cnt0);
            for (int i=0;i<(int)F.size();i++){
                if (mn==mx) val[E[i]] = 0;
                else if (F[i]==mn) val[E[i]] = 1;
                else val[E[i]] = 0;
            }
        }
        else{
            assert(flag3!=-1);
            if (val[flag3]==0) val2--;
            //printf(" %d %d\n", flag3, val2);

            for (int i=0;i<(int)F.size();i++){
                //printf(" %d", F[i]);
                if (F[i]==val2) val[E[i]] = 1;
                else if (F[i]!=INF) val[E[i]] = 0;
            }
        }
        //for (int i=0;i<(int)u.size();i++) printf("%d ", val[i]);
        //printf("\n");
    }
    //printf("YES\n");

    for (int i=0;i<(int)DV.size();i++) if (val[DV[i]]==-1) val[DV[i]] = 1;
    //for (int i=0;i<(int)u.size();i++) printf("%d ", val[i]);
    //printf("\n");

    vector<int> ans;

    for (int i=0;i<n;i++){
        int prv = i;
        while(calc(i, prv+1, n-1) > 0){
            //printf(" %d %d\n", i, prv);
            int l = prv+1, r = n-1;
            while(r-l > 0){
                int m = (l+r)>>1;
                if (calc(i, l, m) > 0) r = m;
                else l = m+1;
            }
            ans.push_back(adj[i][l]);
            prv = l;
        }
    }
    //printf("ans: ");
    //for (auto &x:ans) printf("%d ", x);
    //printf("\n");

    //printf("YES:simurgh\n");

    if ((int)ans.size()!=n-1) exit(1);
    assert(count_common_roads(ans)==n-1);
    //printf("%d\n", cntq);
    assert(cntq<=n*12);

    return ans;
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3148 KB correct
2 Correct 2 ms 3148 KB correct
3 Correct 2 ms 3148 KB correct
4 Correct 2 ms 3148 KB correct
5 Correct 2 ms 3148 KB correct
6 Correct 3 ms 3196 KB correct
7 Correct 1 ms 204 KB correct
8 Correct 2 ms 3148 KB correct
9 Correct 2 ms 3148 KB correct
10 Correct 2 ms 3148 KB correct
11 Correct 2 ms 3148 KB correct
12 Correct 3 ms 3148 KB correct
13 Correct 2 ms 3148 KB correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3148 KB correct
2 Correct 2 ms 3148 KB correct
3 Correct 2 ms 3148 KB correct
4 Correct 2 ms 3148 KB correct
5 Correct 2 ms 3148 KB correct
6 Correct 3 ms 3196 KB correct
7 Correct 1 ms 204 KB correct
8 Correct 2 ms 3148 KB correct
9 Correct 2 ms 3148 KB correct
10 Correct 2 ms 3148 KB correct
11 Correct 2 ms 3148 KB correct
12 Correct 3 ms 3148 KB correct
13 Correct 2 ms 3148 KB correct
14 Correct 3 ms 3276 KB correct
15 Correct 3 ms 3276 KB correct
16 Correct 3 ms 3276 KB correct
17 Correct 3 ms 3276 KB correct
18 Correct 3 ms 3276 KB correct
19 Correct 3 ms 3276 KB correct
20 Correct 3 ms 3276 KB correct
21 Correct 3 ms 3276 KB correct
22 Correct 3 ms 3276 KB correct
23 Correct 3 ms 3276 KB correct
24 Correct 3 ms 3276 KB correct
25 Correct 3 ms 3148 KB correct
26 Correct 4 ms 3276 KB correct
27 Correct 2 ms 3276 KB correct
28 Correct 3 ms 3284 KB correct
29 Correct 3 ms 3148 KB correct
30 Correct 4 ms 3256 KB correct
31 Correct 3 ms 3276 KB correct
32 Correct 3 ms 3276 KB correct
33 Correct 3 ms 3276 KB correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3148 KB correct
2 Correct 2 ms 3148 KB correct
3 Correct 2 ms 3148 KB correct
4 Correct 2 ms 3148 KB correct
5 Correct 2 ms 3148 KB correct
6 Correct 3 ms 3196 KB correct
7 Correct 1 ms 204 KB correct
8 Correct 2 ms 3148 KB correct
9 Correct 2 ms 3148 KB correct
10 Correct 2 ms 3148 KB correct
11 Correct 2 ms 3148 KB correct
12 Correct 3 ms 3148 KB correct
13 Correct 2 ms 3148 KB correct
14 Correct 3 ms 3276 KB correct
15 Correct 3 ms 3276 KB correct
16 Correct 3 ms 3276 KB correct
17 Correct 3 ms 3276 KB correct
18 Correct 3 ms 3276 KB correct
19 Correct 3 ms 3276 KB correct
20 Correct 3 ms 3276 KB correct
21 Correct 3 ms 3276 KB correct
22 Correct 3 ms 3276 KB correct
23 Correct 3 ms 3276 KB correct
24 Correct 3 ms 3276 KB correct
25 Correct 3 ms 3148 KB correct
26 Correct 4 ms 3276 KB correct
27 Correct 2 ms 3276 KB correct
28 Correct 3 ms 3284 KB correct
29 Correct 3 ms 3148 KB correct
30 Correct 4 ms 3256 KB correct
31 Correct 3 ms 3276 KB correct
32 Correct 3 ms 3276 KB correct
33 Correct 3 ms 3276 KB correct
34 Correct 72 ms 3952 KB correct
35 Correct 83 ms 3940 KB correct
36 Correct 55 ms 3660 KB correct
37 Correct 24 ms 3320 KB correct
38 Correct 70 ms 3948 KB correct
39 Correct 61 ms 3848 KB correct
40 Correct 54 ms 3732 KB correct
41 Correct 66 ms 3876 KB correct
42 Correct 65 ms 3952 KB correct
43 Correct 41 ms 3636 KB correct
44 Correct 40 ms 3576 KB correct
45 Correct 46 ms 3612 KB correct
46 Correct 43 ms 3660 KB correct
47 Correct 32 ms 3276 KB correct
48 Correct 21 ms 3288 KB correct
49 Correct 23 ms 3276 KB correct
50 Correct 37 ms 3412 KB correct
51 Correct 46 ms 3624 KB correct
52 Correct 40 ms 3576 KB correct
53 Correct 41 ms 3540 KB correct
54 Correct 45 ms 3628 KB correct
55 Correct 51 ms 3636 KB correct
56 Correct 56 ms 3632 KB correct
57 Correct 47 ms 3620 KB correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB correct
2 Correct 2 ms 3148 KB correct
3 Correct 251 ms 5200 KB correct
4 Correct 513 ms 6268 KB correct
5 Correct 463 ms 6276 KB correct
6 Correct 495 ms 6272 KB correct
7 Correct 479 ms 6264 KB correct
8 Correct 483 ms 6168 KB correct
9 Correct 555 ms 6272 KB correct
10 Correct 517 ms 6272 KB correct
11 Correct 468 ms 6268 KB correct
12 Correct 485 ms 6268 KB correct
13 Correct 2 ms 3148 KB correct
14 Correct 464 ms 6268 KB correct
15 Correct 470 ms 6272 KB correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3148 KB correct
2 Correct 2 ms 3148 KB correct
3 Correct 2 ms 3148 KB correct
4 Correct 2 ms 3148 KB correct
5 Correct 2 ms 3148 KB correct
6 Correct 3 ms 3196 KB correct
7 Correct 1 ms 204 KB correct
8 Correct 2 ms 3148 KB correct
9 Correct 2 ms 3148 KB correct
10 Correct 2 ms 3148 KB correct
11 Correct 2 ms 3148 KB correct
12 Correct 3 ms 3148 KB correct
13 Correct 2 ms 3148 KB correct
14 Correct 3 ms 3276 KB correct
15 Correct 3 ms 3276 KB correct
16 Correct 3 ms 3276 KB correct
17 Correct 3 ms 3276 KB correct
18 Correct 3 ms 3276 KB correct
19 Correct 3 ms 3276 KB correct
20 Correct 3 ms 3276 KB correct
21 Correct 3 ms 3276 KB correct
22 Correct 3 ms 3276 KB correct
23 Correct 3 ms 3276 KB correct
24 Correct 3 ms 3276 KB correct
25 Correct 3 ms 3148 KB correct
26 Correct 4 ms 3276 KB correct
27 Correct 2 ms 3276 KB correct
28 Correct 3 ms 3284 KB correct
29 Correct 3 ms 3148 KB correct
30 Correct 4 ms 3256 KB correct
31 Correct 3 ms 3276 KB correct
32 Correct 3 ms 3276 KB correct
33 Correct 3 ms 3276 KB correct
34 Correct 72 ms 3952 KB correct
35 Correct 83 ms 3940 KB correct
36 Correct 55 ms 3660 KB correct
37 Correct 24 ms 3320 KB correct
38 Correct 70 ms 3948 KB correct
39 Correct 61 ms 3848 KB correct
40 Correct 54 ms 3732 KB correct
41 Correct 66 ms 3876 KB correct
42 Correct 65 ms 3952 KB correct
43 Correct 41 ms 3636 KB correct
44 Correct 40 ms 3576 KB correct
45 Correct 46 ms 3612 KB correct
46 Correct 43 ms 3660 KB correct
47 Correct 32 ms 3276 KB correct
48 Correct 21 ms 3288 KB correct
49 Correct 23 ms 3276 KB correct
50 Correct 37 ms 3412 KB correct
51 Correct 46 ms 3624 KB correct
52 Correct 40 ms 3576 KB correct
53 Correct 41 ms 3540 KB correct
54 Correct 45 ms 3628 KB correct
55 Correct 51 ms 3636 KB correct
56 Correct 56 ms 3632 KB correct
57 Correct 47 ms 3620 KB correct
58 Correct 1 ms 204 KB correct
59 Correct 2 ms 3148 KB correct
60 Correct 251 ms 5200 KB correct
61 Correct 513 ms 6268 KB correct
62 Correct 463 ms 6276 KB correct
63 Correct 495 ms 6272 KB correct
64 Correct 479 ms 6264 KB correct
65 Correct 483 ms 6168 KB correct
66 Correct 555 ms 6272 KB correct
67 Correct 517 ms 6272 KB correct
68 Correct 468 ms 6268 KB correct
69 Correct 485 ms 6268 KB correct
70 Correct 2 ms 3148 KB correct
71 Correct 464 ms 6268 KB correct
72 Correct 470 ms 6272 KB correct
73 Correct 1 ms 312 KB correct
74 Correct 485 ms 7200 KB correct
75 Correct 492 ms 7064 KB correct
76 Correct 181 ms 4688 KB correct
77 Correct 507 ms 7200 KB correct
78 Correct 491 ms 7204 KB correct
79 Correct 506 ms 7192 KB correct
80 Correct 476 ms 7080 KB correct
81 Correct 416 ms 6500 KB correct
82 Correct 467 ms 7068 KB correct
83 Correct 304 ms 5256 KB correct
84 Correct 296 ms 5560 KB correct
85 Correct 282 ms 5348 KB correct
86 Correct 212 ms 4704 KB correct
87 Correct 192 ms 4272 KB correct
88 Correct 172 ms 4188 KB correct
89 Correct 180 ms 4028 KB correct
90 Correct 162 ms 3876 KB correct
91 Correct 106 ms 3352 KB correct
92 Correct 80 ms 3308 KB correct
93 Correct 275 ms 5344 KB correct
94 Correct 208 ms 4684 KB correct
95 Correct 203 ms 4616 KB correct
96 Correct 165 ms 3924 KB correct
97 Correct 178 ms 4064 KB correct
98 Correct 175 ms 4272 KB correct
99 Correct 174 ms 4108 KB correct
100 Correct 109 ms 3488 KB correct
101 Correct 87 ms 3348 KB correct
102 Correct 295 ms 5284 KB correct
103 Correct 302 ms 5256 KB correct
104 Correct 289 ms 5256 KB correct
105 Correct 275 ms 5276 KB correct