oj.uz

Submission #684132

# Submission time Handle Problem Language Result Execution time Memory
684132 2023-01-20T13:57:06 Z 79brue Simurgh (IOI17_simurgh) C++17
100 / 100
 229 ms 15964 KB 
#include "simurgh.h"
#include <bits/stdc++.h>

using namespace std;

struct unionFind{
    int par[502];

    void init(int n){
        for(int i=0; i<n; i++) par[i] = i;
    }

    int find(int x){
        if(par[x] == x) return x;
        return par[x] = find(par[x]);
    }

    void merge(int x, int y){
        x = find(x), y = find(y);
        par[y] = x;
    }
};

struct Edge{
    int s, e, idx;
    Edge(){}
    Edge(int s, int e, int idx): s(s), e(e), idx(idx){}
};

struct Comparison{
    int a, b, v; /// ans[a] - ans[b] = v
    Comparison(){}
    Comparison(int a, int b, int v): a(a), b(b), v(v){}

    bool operator<(const Comparison &r)const{
        return abs(v) > abs(r.v);
    }
};

int n, m;
vector<Edge> link[150002];
int edgeIdx[502][502];
int ex[150002], ey[150002];
bool ans[150002];

void oneTree();
void everyEdge();

vector<int> find_roads(int N, vector<int> u, std::vector<int> v) {
    n = N, m = (int)u.size();
    for(int i=0; i<n; i++) for(int j=0; j<n; j++) edgeIdx[i][j] = -1;
    for(int i=0; i<m; i++){
        link[u[i]].push_back(Edge(u[i], v[i], i));
        link[v[i]].push_back(Edge(v[i], u[i], i));
        ex[i] = u[i], ey[i] = v[i];
        edgeIdx[ex[i]][ey[i]] = i;
        edgeIdx[ey[i]][ex[i]] = i;
    }

    oneTree();
    everyEdge();

    vector<int> ret;
    for(int i=0; i<m; i++) if(ans[i]) ret.push_back(i);
    return ret;
}

vector<Edge> treeLink[150002];
vector<int> treeEdges;
bool inTree[150002];
int depth[150002], par[150002], LCADB[502][10];

bool checked[150002];

void dfs_tree(int x, int p){
    par[x] = p;
    for(Edge y: treeLink[x]){
        if(y.e == p) continue;
        depth[y.e] = depth[x] + 1;
        dfs_tree(y.e, x);
    }
}

int getLCA(int x, int y){
    if(depth[x] > depth[y]) swap(x, y);
    for(int d=9; d>=0; d--) if((depth[y] - depth[x]) & (1<<d)) y = LCADB[y][d];
    if(x==y) return x;
    for(int d=9; d>=0; d--) if(LCADB[x][d] != LCADB[y][d]) x = LCADB[x][d], y = LCADB[y][d];
    return par[x];
}

int finded = 0;
void apply(int x, int t){
    if(checked[x] && ans[x] != t) exit(1);
    if(!checked[x] && t) finded++;
    checked[x] = 1, ans[x] = t;
}

void oneTree(){
    /// 아무 트리나 만들기
    unionFind dsu;
    dsu.init(n);
    for(int i=0; i<m; i++){
        if(dsu.find(ex[i]) != dsu.find(ey[i])){
            dsu.merge(ex[i], ey[i]);
            inTree[i] = 1;
            treeLink[ex[i]].push_back(Edge(ex[i], ey[i], i));
            treeLink[ey[i]].push_back(Edge(ey[i], ex[i], i));
            treeEdges.push_back(i);
        }
    }

    int treeSum = count_common_roads(treeEdges);

    /// 트리를 탐색하기
    dfs_tree(0, -1);
    for(int i=0; i<n; i++) LCADB[i][0] = par[i];
    for(int d=1; d<10; d++) for(int i=0; i<n; i++) LCADB[i][d] = (LCADB[i][d-1] == -1 ? -1 : LCADB[LCADB[i][d-1]][d-1]);

    /// 각 간선이 포함되는지 확인하기
    vector<Comparison> compare;

    for(int edge: treeEdges){
        int u = ex[edge], v = ey[edge];
        if(depth[u] > depth[v]) swap(u, v);

        /// 위로 가는 간선이 있는지 보자
        int up = -1;
        for(int i=0; i<m; i++){
            if(inTree[i]) continue;
            if((getLCA(v, ex[i]) == v) == (getLCA(v, ey[i]) == v)) continue;
            up = i;
            break;
        }
        if(up == -1){
            checked[edge] = 1;
            ans[edge] = 1;
            continue;
        }

        /// 쿼리를 날려 확인해 보자
        vector<int> qv1 = treeEdges;
        qv1.erase(find(qv1.begin(), qv1.end(), edge));
        qv1.push_back(up);
        int qa1 = count_common_roads(qv1);
        compare.push_back(Comparison(edge, up, treeSum - qa1));

        /// 이제 쿼리를 하나 더 날리자
        int top = getLCA(ex[up], ey[up]);
        int highest;
        if(top == ex[up]){
            if(v != ey[up]) highest = edgeIdx[ey[up]][par[ey[up]]];
            else            highest = edgeIdx[par[ey[up]]][par[par[ey[up]]]];
        }
        else if(top == ey[up]){
            if(v != ex[up]) highest = edgeIdx[ex[up]][par[ex[up]]];
            else            highest = edgeIdx[par[ex[up]]][par[par[ex[up]]]];
        }
        else if(v != ex[up]) highest = edgeIdx[ex[up]][par[ex[up]]];
        else if(v != ey[up]) highest = edgeIdx[ey[up]][par[ey[up]]];
        else exit(1);

        vector<int> qv2 = qv1;
        qv2.erase(find(qv2.begin(), qv2.end(), highest));
        qv2.push_back(edge);
        int qa2 = count_common_roads(qv2);
        compare.push_back(Comparison(highest, edge, qa1 - qa2));
    }

    /// 비교 데이터를 바탕으로 결정하자.
    sort(compare.begin(), compare.end());
    for(Comparison com: compare){
        if(com.v){
            if(com.v == 1) apply(com.a, 1), apply(com.b, 0);
            else           apply(com.b, 1), apply(com.a, 0);
        }
        else if(checked[com.a] || checked[com.b]){
            assert(!checked[com.a] || !checked[com.b] || ans[com.a] == ans[com.b]);
            int result = ans[com.a] || ans[com.b];
            apply(com.a, result), apply(com.b, result);
        }
    }

    for(int edge: treeEdges){
        if(!checked[edge]) apply(edge, 0);
    }
}

int dnc(vector<int> &edgeList, int value = -1){
    if(edgeList.empty()) return 0;

    if(value == -1){
        vector<int> qv;
        unionFind dsu;
        dsu.init(n);
        for(auto x: edgeList){
            qv.push_back(x);
            dsu.merge(ex[x], ey[x]);
        }
        int base = 0;
        for(auto x: treeEdges){
            if(dsu.find(ex[x]) == dsu.find(ey[x])) continue;
            base += ans[x];
            qv.push_back(x);
            dsu.merge(ex[x], ey[x]);
        }
        value = count_common_roads(qv) - base;
    }
    if(!value) return value;
    if(value == (int)edgeList.size()){
        for(auto x: edgeList) apply(x, 1);
        return value;
    }

    vector<int> list1, list2;
    int m = (int)edgeList.size() / 2;
    for(int i=0; i<(int)edgeList.size(); i++){
        if(i < m) list1.push_back(edgeList[i]);
        else list2.push_back(edgeList[i]);
    }

    int tmp = value - dnc(list1);
    dnc(list2, tmp);
    return value;
}

void everyEdge(){
    for(int i=0; i<n; i++){
        /// 정점 i 주변의 간선들을 찾을 것이다.
        vector<int> searchTo;
        for(Edge e: link[i]) if(!inTree[e.idx] && !checked[e.idx]) searchTo.push_back(e.idx);
        if(i==236){
            printf("");
        }
        dnc(searchTo);
    }
}

Compilation message

simurgh.cpp: In function 'void everyEdge()':
simurgh.cpp:233:20: warning: zero-length gnu_printf format string [-Wformat-zero-length]
  233 |             printf("");
      |                    ^~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB correct
2 Correct 4 ms 7328 KB correct
3 Correct 4 ms 7380 KB correct
4 Correct 4 ms 7380 KB correct
5 Correct 5 ms 7400 KB correct
6 Correct 4 ms 7380 KB correct
7 Correct 4 ms 7380 KB correct
8 Correct 4 ms 7380 KB correct
9 Correct 4 ms 7380 KB correct
10 Correct 4 ms 7316 KB correct
11 Correct 4 ms 7380 KB correct
12 Correct 4 ms 7380 KB correct
13 Correct 4 ms 7380 KB correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB correct
2 Correct 4 ms 7328 KB correct
3 Correct 4 ms 7380 KB correct
4 Correct 4 ms 7380 KB correct
5 Correct 5 ms 7400 KB correct
6 Correct 4 ms 7380 KB correct
7 Correct 4 ms 7380 KB correct
8 Correct 4 ms 7380 KB correct
9 Correct 4 ms 7380 KB correct
10 Correct 4 ms 7316 KB correct
11 Correct 4 ms 7380 KB correct
12 Correct 4 ms 7380 KB correct
13 Correct 4 ms 7380 KB correct
14 Correct 5 ms 7508 KB correct
15 Correct 4 ms 7476 KB correct
16 Correct 6 ms 7508 KB correct
17 Correct 6 ms 7480 KB correct
18 Correct 7 ms 7508 KB correct
19 Correct 5 ms 7508 KB correct
20 Correct 6 ms 7508 KB correct
21 Correct 6 ms 7508 KB correct
22 Correct 5 ms 7508 KB correct
23 Correct 6 ms 7508 KB correct
24 Correct 5 ms 7508 KB correct
25 Correct 5 ms 7380 KB correct
26 Correct 4 ms 7508 KB correct
27 Correct 5 ms 7508 KB correct
28 Correct 5 ms 7508 KB correct
29 Correct 4 ms 7380 KB correct
30 Correct 5 ms 7508 KB correct
31 Correct 4 ms 7508 KB correct
32 Correct 5 ms 7508 KB correct
33 Correct 5 ms 7472 KB correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB correct
2 Correct 4 ms 7328 KB correct
3 Correct 4 ms 7380 KB correct
4 Correct 4 ms 7380 KB correct
5 Correct 5 ms 7400 KB correct
6 Correct 4 ms 7380 KB correct
7 Correct 4 ms 7380 KB correct
8 Correct 4 ms 7380 KB correct
9 Correct 4 ms 7380 KB correct
10 Correct 4 ms 7316 KB correct
11 Correct 4 ms 7380 KB correct
12 Correct 4 ms 7380 KB correct
13 Correct 4 ms 7380 KB correct
14 Correct 5 ms 7508 KB correct
15 Correct 4 ms 7476 KB correct
16 Correct 6 ms 7508 KB correct
17 Correct 6 ms 7480 KB correct
18 Correct 7 ms 7508 KB correct
19 Correct 5 ms 7508 KB correct
20 Correct 6 ms 7508 KB correct
21 Correct 6 ms 7508 KB correct
22 Correct 5 ms 7508 KB correct
23 Correct 6 ms 7508 KB correct
24 Correct 5 ms 7508 KB correct
25 Correct 5 ms 7380 KB correct
26 Correct 4 ms 7508 KB correct
27 Correct 5 ms 7508 KB correct
28 Correct 5 ms 7508 KB correct
29 Correct 4 ms 7380 KB correct
30 Correct 5 ms 7508 KB correct
31 Correct 4 ms 7508 KB correct
32 Correct 5 ms 7508 KB correct
33 Correct 5 ms 7472 KB correct
34 Correct 45 ms 9428 KB correct
35 Correct 45 ms 9444 KB correct
36 Correct 41 ms 9220 KB correct
37 Correct 17 ms 7908 KB correct
38 Correct 47 ms 9428 KB correct
39 Correct 39 ms 9356 KB correct
40 Correct 37 ms 9240 KB correct
41 Correct 46 ms 9428 KB correct
42 Correct 49 ms 9436 KB correct
43 Correct 18 ms 8940 KB correct
44 Correct 19 ms 8568 KB correct
45 Correct 19 ms 8620 KB correct
46 Correct 19 ms 8532 KB correct
47 Correct 16 ms 8148 KB correct
48 Correct 10 ms 7892 KB correct
49 Correct 14 ms 7996 KB correct
50 Correct 15 ms 8220 KB correct
51 Correct 19 ms 8660 KB correct
52 Correct 20 ms 8576 KB correct
53 Correct 19 ms 8532 KB correct
54 Correct 19 ms 8916 KB correct
55 Correct 19 ms 8660 KB correct
56 Correct 20 ms 8788 KB correct
57 Correct 16 ms 8660 KB correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7396 KB correct
2 Correct 4 ms 7380 KB correct
3 Correct 133 ms 13036 KB correct
4 Correct 211 ms 15004 KB correct
5 Correct 214 ms 15004 KB correct
6 Correct 206 ms 14972 KB correct
7 Correct 131 ms 14924 KB correct
8 Correct 140 ms 15096 KB correct
9 Correct 205 ms 14888 KB correct
10 Correct 208 ms 14924 KB correct
11 Correct 229 ms 14964 KB correct
12 Correct 223 ms 15000 KB correct
13 Correct 3 ms 7380 KB correct
14 Correct 175 ms 14848 KB correct
15 Correct 212 ms 14996 KB correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB correct
2 Correct 4 ms 7328 KB correct
3 Correct 4 ms 7380 KB correct
4 Correct 4 ms 7380 KB correct
5 Correct 5 ms 7400 KB correct
6 Correct 4 ms 7380 KB correct
7 Correct 4 ms 7380 KB correct
8 Correct 4 ms 7380 KB correct
9 Correct 4 ms 7380 KB correct
10 Correct 4 ms 7316 KB correct
11 Correct 4 ms 7380 KB correct
12 Correct 4 ms 7380 KB correct
13 Correct 4 ms 7380 KB correct
14 Correct 5 ms 7508 KB correct
15 Correct 4 ms 7476 KB correct
16 Correct 6 ms 7508 KB correct
17 Correct 6 ms 7480 KB correct
18 Correct 7 ms 7508 KB correct
19 Correct 5 ms 7508 KB correct
20 Correct 6 ms 7508 KB correct
21 Correct 6 ms 7508 KB correct
22 Correct 5 ms 7508 KB correct
23 Correct 6 ms 7508 KB correct
24 Correct 5 ms 7508 KB correct
25 Correct 5 ms 7380 KB correct
26 Correct 4 ms 7508 KB correct
27 Correct 5 ms 7508 KB correct
28 Correct 5 ms 7508 KB correct
29 Correct 4 ms 7380 KB correct
30 Correct 5 ms 7508 KB correct
31 Correct 4 ms 7508 KB correct
32 Correct 5 ms 7508 KB correct
33 Correct 5 ms 7472 KB correct
34 Correct 45 ms 9428 KB correct
35 Correct 45 ms 9444 KB correct
36 Correct 41 ms 9220 KB correct
37 Correct 17 ms 7908 KB correct
38 Correct 47 ms 9428 KB correct
39 Correct 39 ms 9356 KB correct
40 Correct 37 ms 9240 KB correct
41 Correct 46 ms 9428 KB correct
42 Correct 49 ms 9436 KB correct
43 Correct 18 ms 8940 KB correct
44 Correct 19 ms 8568 KB correct
45 Correct 19 ms 8620 KB correct
46 Correct 19 ms 8532 KB correct
47 Correct 16 ms 8148 KB correct
48 Correct 10 ms 7892 KB correct
49 Correct 14 ms 7996 KB correct
50 Correct 15 ms 8220 KB correct
51 Correct 19 ms 8660 KB correct
52 Correct 20 ms 8576 KB correct
53 Correct 19 ms 8532 KB correct
54 Correct 19 ms 8916 KB correct
55 Correct 19 ms 8660 KB correct
56 Correct 20 ms 8788 KB correct
57 Correct 16 ms 8660 KB correct
58 Correct 3 ms 7396 KB correct
59 Correct 4 ms 7380 KB correct
60 Correct 133 ms 13036 KB correct
61 Correct 211 ms 15004 KB correct
62 Correct 214 ms 15004 KB correct
63 Correct 206 ms 14972 KB correct
64 Correct 131 ms 14924 KB correct
65 Correct 140 ms 15096 KB correct
66 Correct 205 ms 14888 KB correct
67 Correct 208 ms 14924 KB correct
68 Correct 229 ms 14964 KB correct
69 Correct 223 ms 15000 KB correct
70 Correct 3 ms 7380 KB correct
71 Correct 175 ms 14848 KB correct
72 Correct 212 ms 14996 KB correct
73 Correct 4 ms 7380 KB correct
74 Correct 217 ms 14932 KB correct
75 Correct 202 ms 15608 KB correct
76 Correct 112 ms 11104 KB correct
77 Correct 208 ms 15964 KB correct
78 Correct 212 ms 15884 KB correct
79 Correct 227 ms 15900 KB correct
80 Correct 206 ms 15704 KB correct
81 Correct 138 ms 15160 KB correct
82 Correct 221 ms 15728 KB correct
83 Correct 168 ms 12608 KB correct
84 Correct 80 ms 13408 KB correct
85 Correct 68 ms 13148 KB correct
86 Correct 66 ms 11316 KB correct
87 Correct 60 ms 10920 KB correct
88 Correct 57 ms 10068 KB correct
89 Correct 61 ms 9980 KB correct
90 Correct 60 ms 9804 KB correct
91 Correct 49 ms 8620 KB correct
92 Correct 31 ms 8404 KB correct
93 Correct 66 ms 13144 KB correct
94 Correct 67 ms 11348 KB correct
95 Correct 59 ms 11436 KB correct
96 Correct 55 ms 9940 KB correct
97 Correct 63 ms 10040 KB correct
98 Correct 58 ms 10836 KB correct
99 Correct 58 ms 9940 KB correct
100 Correct 50 ms 8836 KB correct
101 Correct 33 ms 8496 KB correct
102 Correct 58 ms 11972 KB correct
103 Correct 65 ms 12172 KB correct
104 Correct 57 ms 11932 KB correct
105 Correct 64 ms 11900 KB correct