제출 #684132

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
684132		79brue	Simurgh (IOI17_simurgh)	C++17	100 / 100	229 ms	15964 KiB

simurgh

#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);
    }
}

컴파일 시 표준 에러 (stderr) 메시지

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 / 13
• Subtask 2: 17 / 17
• Subtask 3: 21 / 21
• Subtask 4: 19 / 19
• Subtask 5: 30 / 30