oj.uz

Submission #491350

# Submission time Handle Problem Language Result Execution time Memory
491350 2021-12-01T17:18:37 Z qwerasdfzxcl Simurgh (IOI17_simurgh) C++14
51 / 100
 255 ms 5108 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[100100], dfs_chk[100100];
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++;
    }

    return count_common_roads(Q) - cnt;
}

std::vector<int> find_roads(int N, std::vector<int> u, std::vector<int> v) {
    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+100100, -1);
    fill(dfs_chk, dfs_chk+100100, 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");
    int cntq = 0;

    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++;
            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");
    assert(cntq<=n*2);

    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);

    return ans;
}

Subtask #1
13.0 / 13.0

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

Subtask #2
17.0 / 17.0

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

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1996 KB correct
2 Correct 1 ms 1996 KB correct
3 Correct 1 ms 1996 KB correct
4 Correct 1 ms 1996 KB correct
5 Correct 1 ms 1996 KB correct
6 Correct 1 ms 1996 KB correct
7 Correct 0 ms 204 KB correct
8 Correct 1 ms 1996 KB correct
9 Correct 1 ms 1996 KB correct
10 Correct 1 ms 1996 KB correct
11 Correct 1 ms 1996 KB correct
12 Correct 1 ms 1996 KB correct
13 Correct 1 ms 1996 KB correct
14 Correct 2 ms 1996 KB correct
15 Correct 2 ms 1996 KB correct
16 Correct 2 ms 1996 KB correct
17 Correct 2 ms 1996 KB correct
18 Correct 2 ms 1996 KB correct
19 Correct 4 ms 1996 KB correct
20 Correct 3 ms 1996 KB correct
21 Correct 2 ms 2108 KB correct
22 Correct 2 ms 1996 KB correct
23 Correct 2 ms 1996 KB correct
24 Correct 2 ms 1996 KB correct
25 Correct 2 ms 1996 KB correct
26 Correct 3 ms 1996 KB correct
27 Correct 3 ms 1996 KB correct
28 Correct 2 ms 1996 KB correct
29 Correct 2 ms 1996 KB correct
30 Correct 2 ms 1996 KB correct
31 Correct 2 ms 1996 KB correct
32 Correct 2 ms 1996 KB correct
33 Correct 2 ms 1996 KB correct
34 Correct 62 ms 2780 KB correct
35 Correct 59 ms 2764 KB correct
36 Correct 48 ms 2508 KB correct
37 Correct 21 ms 2140 KB correct
38 Correct 60 ms 2884 KB correct
39 Correct 58 ms 2664 KB correct
40 Correct 47 ms 2508 KB correct
41 Correct 58 ms 2764 KB correct
42 Correct 65 ms 2768 KB correct
43 Correct 39 ms 2380 KB correct
44 Correct 40 ms 2372 KB correct
45 Correct 41 ms 2380 KB correct
46 Correct 35 ms 2252 KB correct
47 Correct 27 ms 2124 KB correct
48 Correct 19 ms 2108 KB correct
49 Correct 21 ms 2124 KB correct
50 Correct 29 ms 2124 KB correct
51 Correct 46 ms 2380 KB correct
52 Correct 36 ms 2380 KB correct
53 Correct 35 ms 2360 KB correct
54 Correct 41 ms 2456 KB correct
55 Correct 43 ms 2448 KB correct
56 Correct 40 ms 2380 KB correct
57 Correct 42 ms 2380 KB correct

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB correct
2 Correct 1 ms 1996 KB correct
3 Correct 239 ms 4024 KB correct
4 Incorrect 255 ms 5108 KB WA in grader: NO
5 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1996 KB correct
2 Correct 1 ms 1996 KB correct
3 Correct 1 ms 1996 KB correct
4 Correct 1 ms 1996 KB correct
5 Correct 1 ms 1996 KB correct
6 Correct 1 ms 1996 KB correct
7 Correct 0 ms 204 KB correct
8 Correct 1 ms 1996 KB correct
9 Correct 1 ms 1996 KB correct
10 Correct 1 ms 1996 KB correct
11 Correct 1 ms 1996 KB correct
12 Correct 1 ms 1996 KB correct
13 Correct 1 ms 1996 KB correct
14 Correct 2 ms 1996 KB correct
15 Correct 2 ms 1996 KB correct
16 Correct 2 ms 1996 KB correct
17 Correct 2 ms 1996 KB correct
18 Correct 2 ms 1996 KB correct
19 Correct 4 ms 1996 KB correct
20 Correct 3 ms 1996 KB correct
21 Correct 2 ms 2108 KB correct
22 Correct 2 ms 1996 KB correct
23 Correct 2 ms 1996 KB correct
24 Correct 2 ms 1996 KB correct
25 Correct 2 ms 1996 KB correct
26 Correct 3 ms 1996 KB correct
27 Correct 3 ms 1996 KB correct
28 Correct 2 ms 1996 KB correct
29 Correct 2 ms 1996 KB correct
30 Correct 2 ms 1996 KB correct
31 Correct 2 ms 1996 KB correct
32 Correct 2 ms 1996 KB correct
33 Correct 2 ms 1996 KB correct
34 Correct 62 ms 2780 KB correct
35 Correct 59 ms 2764 KB correct
36 Correct 48 ms 2508 KB correct
37 Correct 21 ms 2140 KB correct
38 Correct 60 ms 2884 KB correct
39 Correct 58 ms 2664 KB correct
40 Correct 47 ms 2508 KB correct
41 Correct 58 ms 2764 KB correct
42 Correct 65 ms 2768 KB correct
43 Correct 39 ms 2380 KB correct
44 Correct 40 ms 2372 KB correct
45 Correct 41 ms 2380 KB correct
46 Correct 35 ms 2252 KB correct
47 Correct 27 ms 2124 KB correct
48 Correct 19 ms 2108 KB correct
49 Correct 21 ms 2124 KB correct
50 Correct 29 ms 2124 KB correct
51 Correct 46 ms 2380 KB correct
52 Correct 36 ms 2380 KB correct
53 Correct 35 ms 2360 KB correct
54 Correct 41 ms 2456 KB correct
55 Correct 43 ms 2448 KB correct
56 Correct 40 ms 2380 KB correct
57 Correct 42 ms 2380 KB correct
58 Correct 0 ms 204 KB correct
59 Correct 1 ms 1996 KB correct
60 Correct 239 ms 4024 KB correct
61 Incorrect 255 ms 5108 KB WA in grader: NO
62 Halted 0 ms 0 KB -