oj.uz

Submission #491353

# Submission time Handle Problem Language Result Execution time Memory
491353 2021-12-01T17:26:22 Z qwerasdfzxcl Simurgh (IOI17_simurgh) C++14
51 / 100
 290 ms 5088 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], 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++;

    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+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");
    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++;
            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 1 ms 1996 KB correct
2 Correct 2 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 2 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 3 ms 1996 KB correct
15 Correct 3 ms 1996 KB correct
16 Correct 2 ms 1996 KB correct
17 Correct 3 ms 1996 KB correct
18 Correct 2 ms 1996 KB correct
19 Correct 3 ms 1996 KB correct
20 Correct 2 ms 1996 KB correct
21 Correct 2 ms 1996 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 2 ms 1996 KB correct
27 Correct 2 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 2092 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 2 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 3 ms 1996 KB correct
15 Correct 3 ms 1996 KB correct
16 Correct 2 ms 1996 KB correct
17 Correct 3 ms 1996 KB correct
18 Correct 2 ms 1996 KB correct
19 Correct 3 ms 1996 KB correct
20 Correct 2 ms 1996 KB correct
21 Correct 2 ms 1996 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 2 ms 1996 KB correct
27 Correct 2 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 2092 KB correct
32 Correct 2 ms 1996 KB correct
33 Correct 2 ms 1996 KB correct
34 Correct 65 ms 2776 KB correct
35 Correct 62 ms 2748 KB correct
36 Correct 49 ms 2564 KB correct
37 Correct 19 ms 2140 KB correct
38 Correct 59 ms 2768 KB correct
39 Correct 62 ms 2664 KB correct
40 Correct 59 ms 2508 KB correct
41 Correct 72 ms 2768 KB correct
42 Correct 62 ms 2776 KB correct
43 Correct 38 ms 2444 KB correct
44 Correct 38 ms 2392 KB correct
45 Correct 42 ms 2380 KB correct
46 Correct 41 ms 2360 KB correct
47 Correct 30 ms 2196 KB correct
48 Correct 18 ms 2112 KB correct
49 Correct 20 ms 2132 KB correct
50 Correct 28 ms 2216 KB correct
51 Correct 43 ms 2444 KB correct
52 Correct 35 ms 2380 KB correct
53 Correct 37 ms 2252 KB correct
54 Correct 43 ms 2452 KB correct
55 Correct 44 ms 2448 KB correct
56 Correct 51 ms 2444 KB correct
57 Correct 43 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 256 ms 4016 KB correct
4 Incorrect 290 ms 5088 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 2 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 3 ms 1996 KB correct
15 Correct 3 ms 1996 KB correct
16 Correct 2 ms 1996 KB correct
17 Correct 3 ms 1996 KB correct
18 Correct 2 ms 1996 KB correct
19 Correct 3 ms 1996 KB correct
20 Correct 2 ms 1996 KB correct
21 Correct 2 ms 1996 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 2 ms 1996 KB correct
27 Correct 2 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 2092 KB correct
32 Correct 2 ms 1996 KB correct
33 Correct 2 ms 1996 KB correct
34 Correct 65 ms 2776 KB correct
35 Correct 62 ms 2748 KB correct
36 Correct 49 ms 2564 KB correct
37 Correct 19 ms 2140 KB correct
38 Correct 59 ms 2768 KB correct
39 Correct 62 ms 2664 KB correct
40 Correct 59 ms 2508 KB correct
41 Correct 72 ms 2768 KB correct
42 Correct 62 ms 2776 KB correct
43 Correct 38 ms 2444 KB correct
44 Correct 38 ms 2392 KB correct
45 Correct 42 ms 2380 KB correct
46 Correct 41 ms 2360 KB correct
47 Correct 30 ms 2196 KB correct
48 Correct 18 ms 2112 KB correct
49 Correct 20 ms 2132 KB correct
50 Correct 28 ms 2216 KB correct
51 Correct 43 ms 2444 KB correct
52 Correct 35 ms 2380 KB correct
53 Correct 37 ms 2252 KB correct
54 Correct 43 ms 2452 KB correct
55 Correct 44 ms 2448 KB correct
56 Correct 51 ms 2444 KB correct
57 Correct 43 ms 2380 KB correct
58 Correct 0 ms 204 KB correct
59 Correct 1 ms 1996 KB correct
60 Correct 256 ms 4016 KB correct
61 Incorrect 290 ms 5088 KB WA in grader: NO
62 Halted 0 ms 0 KB -