oj.uz

Submission #491356

# Submission time Handle Problem Language Result Execution time Memory
491356 2021-12-01T17:27:40 Z qwerasdfzxcl Simurgh (IOI17_simurgh) C++14
51 / 100
 285 ms 5092 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++;
    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+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++;
            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 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 2 ms 1996 KB correct
6 Correct 2 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 2 ms 1996 KB correct
12 Correct 2 ms 1996 KB correct
13 Correct 2 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 2 ms 1996 KB correct
6 Correct 2 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 2 ms 1996 KB correct
12 Correct 2 ms 1996 KB correct
13 Correct 2 ms 1996 KB correct
14 Correct 3 ms 2116 KB correct
15 Correct 4 ms 2124 KB correct
16 Correct 2 ms 1996 KB correct
17 Correct 3 ms 1996 KB correct
18 Correct 3 ms 2028 KB correct
19 Correct 2 ms 2116 KB correct
20 Correct 3 ms 1996 KB correct
21 Correct 3 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 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 3 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 2 ms 1996 KB correct
3 Correct 1 ms 1996 KB correct
4 Correct 1 ms 1996 KB correct
5 Correct 2 ms 1996 KB correct
6 Correct 2 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 2 ms 1996 KB correct
12 Correct 2 ms 1996 KB correct
13 Correct 2 ms 1996 KB correct
14 Correct 3 ms 2116 KB correct
15 Correct 4 ms 2124 KB correct
16 Correct 2 ms 1996 KB correct
17 Correct 3 ms 1996 KB correct
18 Correct 3 ms 2028 KB correct
19 Correct 2 ms 2116 KB correct
20 Correct 3 ms 1996 KB correct
21 Correct 3 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 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 3 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 69 ms 2772 KB correct
35 Correct 62 ms 2752 KB correct
36 Correct 53 ms 2568 KB correct
37 Correct 20 ms 2140 KB correct
38 Correct 72 ms 2760 KB correct
39 Correct 64 ms 2636 KB correct
40 Correct 52 ms 2548 KB correct
41 Correct 66 ms 2772 KB correct
42 Correct 68 ms 2764 KB correct
43 Correct 46 ms 2380 KB correct
44 Correct 39 ms 2380 KB correct
45 Correct 46 ms 2380 KB correct
46 Correct 41 ms 2360 KB correct
47 Correct 33 ms 2124 KB correct
48 Correct 20 ms 1996 KB correct
49 Correct 22 ms 2136 KB correct
50 Correct 30 ms 2124 KB correct
51 Correct 44 ms 2448 KB correct
52 Correct 38 ms 2380 KB correct
53 Correct 44 ms 2360 KB correct
54 Correct 41 ms 2444 KB correct
55 Correct 45 ms 2448 KB correct
56 Correct 46 ms 2380 KB correct
57 Correct 45 ms 2380 KB correct

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB correct
2 Correct 1 ms 1996 KB correct
3 Correct 280 ms 4024 KB correct
4 Incorrect 285 ms 5092 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 2 ms 1996 KB correct
6 Correct 2 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 2 ms 1996 KB correct
12 Correct 2 ms 1996 KB correct
13 Correct 2 ms 1996 KB correct
14 Correct 3 ms 2116 KB correct
15 Correct 4 ms 2124 KB correct
16 Correct 2 ms 1996 KB correct
17 Correct 3 ms 1996 KB correct
18 Correct 3 ms 2028 KB correct
19 Correct 2 ms 2116 KB correct
20 Correct 3 ms 1996 KB correct
21 Correct 3 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 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 3 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 69 ms 2772 KB correct
35 Correct 62 ms 2752 KB correct
36 Correct 53 ms 2568 KB correct
37 Correct 20 ms 2140 KB correct
38 Correct 72 ms 2760 KB correct
39 Correct 64 ms 2636 KB correct
40 Correct 52 ms 2548 KB correct
41 Correct 66 ms 2772 KB correct
42 Correct 68 ms 2764 KB correct
43 Correct 46 ms 2380 KB correct
44 Correct 39 ms 2380 KB correct
45 Correct 46 ms 2380 KB correct
46 Correct 41 ms 2360 KB correct
47 Correct 33 ms 2124 KB correct
48 Correct 20 ms 1996 KB correct
49 Correct 22 ms 2136 KB correct
50 Correct 30 ms 2124 KB correct
51 Correct 44 ms 2448 KB correct
52 Correct 38 ms 2380 KB correct
53 Correct 44 ms 2360 KB correct
54 Correct 41 ms 2444 KB correct
55 Correct 45 ms 2448 KB correct
56 Correct 46 ms 2380 KB correct
57 Correct 45 ms 2380 KB correct
58 Correct 1 ms 204 KB correct
59 Correct 1 ms 1996 KB correct
60 Correct 280 ms 4024 KB correct
61 Incorrect 285 ms 5092 KB WA in grader: NO
62 Halted 0 ms 0 KB -