oj.uz

Submission #491349

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

    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 2 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 2 ms 1996 KB correct
10 Correct 2 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 2 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 2 ms 1996 KB correct
10 Correct 2 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 3 ms 2112 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 2 ms 1996 KB correct
20 Correct 3 ms 1996 KB correct
21 Correct 2 ms 1996 KB correct
22 Correct 2 ms 2104 KB correct
23 Correct 3 ms 1996 KB correct
24 Correct 3 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 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 2 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 2 ms 1996 KB correct
10 Correct 2 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 3 ms 2112 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 2 ms 1996 KB correct
20 Correct 3 ms 1996 KB correct
21 Correct 2 ms 1996 KB correct
22 Correct 2 ms 2104 KB correct
23 Correct 3 ms 1996 KB correct
24 Correct 3 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 1996 KB correct
32 Correct 2 ms 1996 KB correct
33 Correct 2 ms 1996 KB correct
34 Correct 61 ms 2764 KB correct
35 Correct 64 ms 2744 KB correct
36 Correct 55 ms 2536 KB correct
37 Correct 25 ms 2124 KB correct
38 Correct 60 ms 2764 KB correct
39 Correct 56 ms 2668 KB correct
40 Correct 48 ms 2508 KB correct
41 Correct 60 ms 2816 KB correct
42 Correct 65 ms 2772 KB correct
43 Correct 55 ms 2448 KB correct
44 Correct 37 ms 2392 KB correct
45 Correct 40 ms 2440 KB correct
46 Correct 35 ms 2252 KB correct
47 Correct 28 ms 2124 KB correct
48 Correct 18 ms 2112 KB correct
49 Correct 22 ms 2136 KB correct
50 Correct 39 ms 2220 KB correct
51 Correct 45 ms 2444 KB correct
52 Correct 39 ms 2400 KB correct
53 Correct 37 ms 2252 KB correct
54 Correct 44 ms 2460 KB correct
55 Correct 43 ms 2380 KB correct
56 Correct 46 ms 2452 KB correct
57 Correct 48 ms 2456 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 4020 KB correct
4 Incorrect 299 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 1 ms 1996 KB correct
3 Correct 1 ms 1996 KB correct
4 Correct 2 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 2 ms 1996 KB correct
10 Correct 2 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 3 ms 2112 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 2 ms 1996 KB correct
20 Correct 3 ms 1996 KB correct
21 Correct 2 ms 1996 KB correct
22 Correct 2 ms 2104 KB correct
23 Correct 3 ms 1996 KB correct
24 Correct 3 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 1996 KB correct
32 Correct 2 ms 1996 KB correct
33 Correct 2 ms 1996 KB correct
34 Correct 61 ms 2764 KB correct
35 Correct 64 ms 2744 KB correct
36 Correct 55 ms 2536 KB correct
37 Correct 25 ms 2124 KB correct
38 Correct 60 ms 2764 KB correct
39 Correct 56 ms 2668 KB correct
40 Correct 48 ms 2508 KB correct
41 Correct 60 ms 2816 KB correct
42 Correct 65 ms 2772 KB correct
43 Correct 55 ms 2448 KB correct
44 Correct 37 ms 2392 KB correct
45 Correct 40 ms 2440 KB correct
46 Correct 35 ms 2252 KB correct
47 Correct 28 ms 2124 KB correct
48 Correct 18 ms 2112 KB correct
49 Correct 22 ms 2136 KB correct
50 Correct 39 ms 2220 KB correct
51 Correct 45 ms 2444 KB correct
52 Correct 39 ms 2400 KB correct
53 Correct 37 ms 2252 KB correct
54 Correct 44 ms 2460 KB correct
55 Correct 43 ms 2380 KB correct
56 Correct 46 ms 2452 KB correct
57 Correct 48 ms 2456 KB correct
58 Correct 0 ms 204 KB correct
59 Correct 1 ms 1996 KB correct
60 Correct 239 ms 4020 KB correct
61 Incorrect 299 ms 5092 KB WA in grader: NO
62 Halted 0 ms 0 KB -