제출 #891674

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
891674		vjudge1	통행료 (IOI18_highway)	C++17	51 / 100	203 ms	262144 KiB

highway

#include "highway.h"
#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;
using ii = pair<int, int>;
vector<ii> E;

struct tree {
    int n;
    vi par, par_cent, sz;
    vector<vi> L, G;
    
    tree(int N) : n(N), L(N), par(N), par_cent(N), sz(N), G(N) {}

    void add_edge(int u, int v) {
        L[u].push_back(v);
        L[v].push_back(u);
    }

    void init() {
        vi on(n, 1);
        function<void(int, int)> dfs_sz = [&](int u, int p) {
            sz[u] = 1;
            for(auto it : L[u]) {
                if(on[it] && it != p) {
                    dfs_sz(it, u);
                    sz[u] += sz[it];
                }
            }
        };

        function<int(int, int, int)> find_c = [&](int u, int p, int slim) {
            for(auto it : L[u])
                if(on[it] && it != p && 2 * sz[it] > slim) return find_c(it, u, slim);
            return u;
        };

        function<void(int, int) > dfs_cent = [&](int u, int pc) {
            dfs_sz(u, -1);
            int c = find_c(u, -1, sz[u]);
            on[c] = 0;
            par_cent[c] = pc;
            if(pc != -1) {
                G[pc].push_back(c);
            }
            for(auto it : L[c])
                if(on[it]) dfs_cent(it, c);
        };

        dfs_cent(0, -1);
    }

    void solve() {
        function<void(int, int, vi&)> dfs_comp = [&](int u, int p, vi& V) {
            V.push_back(u);
            for(auto it : G[u])
                dfs_comp(it, u, V);
        };
        int cost_baza = ask(vi(E.size(), 0));
        auto dif = [&](int u, vector<vi>& Fii, int st, int dr) {
            set<int> S = {u};
            for(int i = st; i <= dr; ++i)
                for(auto it : Fii[i]) S.insert(it);
            vi w;
            for(auto [u, v] : E) {
                if(S.count(u) + S.count(v))
                    w.push_back(1);
                else
                    w.push_back(0); 
            }
            return ask(w) - cost_baza;
        };
        vi capete;
        function<void(int, int, int)> dfs_solve = [&](int c, int pc, int nr) {
            vector<vi> comp_fii;
            for(auto it : G[c]) {
                comp_fii.push_back(vi());
                dfs_comp(it, c, comp_fii.back());
            }
            int pst = -1, pdr = comp_fii.size(), nrfii = comp_fii.size();

            int v = dif(c, comp_fii, 0, nrfii - 1);
            if(!v) {
                if(nr == 1) { // v e unul dintre s & t 
                    capete.push_back(v);
                    return;
                } else {
                    ///uhhh, wtf?
                    assert(0);
                }
            }
            for(int step = 31 - __builtin_clz(nrfii); step >= 0; --step) {
                if(pst + (1 << step) < nrfii) {
                    if(!dif(c, comp_fii, 0, pst + (1 << step)))
                        pst += (1 << step);
                }
                if(pdr - (1 << step) >= 0) {
                    if(!dif(c, comp_fii, pdr - (1 << step), nrfii - 1))
                        pdr -= (1 << step);
                }
            }
            ++pst;
            --pdr;

        };
        assert(capete.size() == 2);
    }

    int cine(int rad) {
        vi niv(n);
        function<void(int, int, int)> dfs = [&](int u, int p, int li) {
            niv[u] = li;
            for(auto it : L[u]) {
                if(it != p) {
                    dfs(it, u, li + 1);
                }
            }
        };
        vi re;
        for(int i = 0; i < n; ++i) {
            re.push_back(i);
        }
        dfs(rad, -1, 0);
        sort(re.begin(), re.end(), [&](int a, int b) { return niv[a] < niv[b]; });
        int st = 0, dr = n - 1, mij;
        int q0 = 0;
        auto query = [&](int p) {
            static vi used(n, 0);
            for(int i = 0; i < n; ++i)
                used[i] = 0;
            for(int i = 0; i <= p; ++i)
                used[re[i]] = 1;
            vi w;
            for(auto [u, v] : E) {
                if(used[u] && used[v]) w.push_back(1);
                else w.push_back(0);
            }
            int v = ask(w) - q0;
            return v + q0;
        };
        q0 = query(dr);
        int cm = query(dr);
        while(st < dr) {
            mij = (st + dr) / 2;
            if(query(mij) == q0) {
                dr = mij;
            } else 
                st = mij + 1;
        }
        return re[st];
    }
};

void find_pair(int N, vi U, vi V, int A, int B) {
    tree T(N);
    for(int i = 0; i < U.size(); ++i) {
        T.add_edge(U[i], V[i]);
        E.push_back({U[i], V[i]});
    }
    T.init();
    int s = T.cine(0);
    int t = T.cine(s);
    answer(s, t);
}

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

highway.cpp: In constructor 'tree::tree(int)':
highway.cpp:13:16: warning: 'tree::L' will be initialized after [-Wreorder]
   13 |     vector<vi> L, G;
      |                ^
highway.cpp:12:8: warning:   'vi tree::par' [-Wreorder]
   12 |     vi par, par_cent, sz;
      |        ^~~
highway.cpp:15:5: warning:   when initialized here [-Wreorder]
   15 |     tree(int N) : n(N), L(N), par(N), par_cent(N), sz(N), G(N) {}
      |     ^~~~
highway.cpp: In member function 'int tree::cine(int)':
highway.cpp:144:13: warning: unused variable 'cm' [-Wunused-variable]
  144 |         int cm = query(dr);
      |             ^~
highway.cpp: In function 'void find_pair(int, vi, vi, int, int)':
highway.cpp:158:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  158 |     for(int i = 0; i < U.size(); ++i) {
      |                    ~~^~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 6 / 6
• Subtask 4: 33 / 33
• Subtask 5: 0 / 18
• Subtask 6: 0 / 31