oj.uz

Submission #491346

# Submission time Handle Problem Language Result Execution time Memory
491346 2021-12-01T17:09:45 Z qwerasdfzxcl Simurgh (IOI17_simurgh) C++14
51 / 100
 255 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];
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");

    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));
            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);
            if (mn==mx) continue;
            for (int i=0;i<(int)F.size();i++){
                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);

    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 1 ms 1996 KB correct
7 Correct 1 ms 204 KB correct
8 Correct 2 ms 1996 KB correct
9 Correct 2 ms 2012 KB correct
10 Correct 1 ms 1996 KB correct
11 Correct 2 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 2 ms 1996 KB correct
6 Correct 1 ms 1996 KB correct
7 Correct 1 ms 204 KB correct
8 Correct 2 ms 1996 KB correct
9 Correct 2 ms 2012 KB correct
10 Correct 1 ms 1996 KB correct
11 Correct 2 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 2124 KB correct
16 Correct 3 ms 2124 KB correct
17 Correct 2 ms 2124 KB correct
18 Correct 3 ms 1996 KB correct
19 Correct 3 ms 1996 KB correct
20 Correct 3 ms 2124 KB correct
21 Correct 3 ms 1996 KB correct
22 Correct 3 ms 1996 KB correct
23 Correct 3 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 2100 KB correct
28 Correct 2 ms 2108 KB correct
29 Correct 2 ms 2104 KB correct
30 Correct 2 ms 1996 KB correct
31 Correct 3 ms 1996 KB correct
32 Correct 2 ms 1996 KB correct
33 Correct 2 ms 2104 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 1 ms 1996 KB correct
7 Correct 1 ms 204 KB correct
8 Correct 2 ms 1996 KB correct
9 Correct 2 ms 2012 KB correct
10 Correct 1 ms 1996 KB correct
11 Correct 2 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 2124 KB correct
16 Correct 3 ms 2124 KB correct
17 Correct 2 ms 2124 KB correct
18 Correct 3 ms 1996 KB correct
19 Correct 3 ms 1996 KB correct
20 Correct 3 ms 2124 KB correct
21 Correct 3 ms 1996 KB correct
22 Correct 3 ms 1996 KB correct
23 Correct 3 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 2100 KB correct
28 Correct 2 ms 2108 KB correct
29 Correct 2 ms 2104 KB correct
30 Correct 2 ms 1996 KB correct
31 Correct 3 ms 1996 KB correct
32 Correct 2 ms 1996 KB correct
33 Correct 2 ms 2104 KB correct
34 Correct 61 ms 2972 KB correct
35 Correct 67 ms 3084 KB correct
36 Correct 52 ms 2636 KB correct
37 Correct 21 ms 2124 KB correct
38 Correct 65 ms 2908 KB correct
39 Correct 58 ms 2764 KB correct
40 Correct 48 ms 2636 KB correct
41 Correct 62 ms 2980 KB correct
42 Correct 72 ms 2980 KB correct
43 Correct 39 ms 2568 KB correct
44 Correct 37 ms 2380 KB correct
45 Correct 44 ms 2508 KB correct
46 Correct 34 ms 2432 KB correct
47 Correct 27 ms 2124 KB correct
48 Correct 18 ms 1996 KB correct
49 Correct 20 ms 2156 KB correct
50 Correct 26 ms 2244 KB correct
51 Correct 42 ms 2528 KB correct
52 Correct 36 ms 2480 KB correct
53 Correct 37 ms 2380 KB correct
54 Correct 43 ms 2548 KB correct
55 Correct 42 ms 2540 KB correct
56 Correct 46 ms 2508 KB correct
57 Correct 44 ms 2556 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 248 ms 4020 KB correct
4 Incorrect 255 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 2 ms 1996 KB correct
6 Correct 1 ms 1996 KB correct
7 Correct 1 ms 204 KB correct
8 Correct 2 ms 1996 KB correct
9 Correct 2 ms 2012 KB correct
10 Correct 1 ms 1996 KB correct
11 Correct 2 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 2124 KB correct
16 Correct 3 ms 2124 KB correct
17 Correct 2 ms 2124 KB correct
18 Correct 3 ms 1996 KB correct
19 Correct 3 ms 1996 KB correct
20 Correct 3 ms 2124 KB correct
21 Correct 3 ms 1996 KB correct
22 Correct 3 ms 1996 KB correct
23 Correct 3 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 2100 KB correct
28 Correct 2 ms 2108 KB correct
29 Correct 2 ms 2104 KB correct
30 Correct 2 ms 1996 KB correct
31 Correct 3 ms 1996 KB correct
32 Correct 2 ms 1996 KB correct
33 Correct 2 ms 2104 KB correct
34 Correct 61 ms 2972 KB correct
35 Correct 67 ms 3084 KB correct
36 Correct 52 ms 2636 KB correct
37 Correct 21 ms 2124 KB correct
38 Correct 65 ms 2908 KB correct
39 Correct 58 ms 2764 KB correct
40 Correct 48 ms 2636 KB correct
41 Correct 62 ms 2980 KB correct
42 Correct 72 ms 2980 KB correct
43 Correct 39 ms 2568 KB correct
44 Correct 37 ms 2380 KB correct
45 Correct 44 ms 2508 KB correct
46 Correct 34 ms 2432 KB correct
47 Correct 27 ms 2124 KB correct
48 Correct 18 ms 1996 KB correct
49 Correct 20 ms 2156 KB correct
50 Correct 26 ms 2244 KB correct
51 Correct 42 ms 2528 KB correct
52 Correct 36 ms 2480 KB correct
53 Correct 37 ms 2380 KB correct
54 Correct 43 ms 2548 KB correct
55 Correct 42 ms 2540 KB correct
56 Correct 46 ms 2508 KB correct
57 Correct 44 ms 2556 KB correct
58 Correct 0 ms 204 KB correct
59 Correct 1 ms 1996 KB correct
60 Correct 248 ms 4020 KB correct
61 Incorrect 255 ms 5088 KB WA in grader: NO
62 Halted 0 ms 0 KB -