Submission #1285206

#	Time	Username	Problem	Language	Result	Execution time	Memory
1285206		mariaclara	통행료 (IOI18_highway)	C++17	5 / 100	1463 ms	327680 KiB

highway

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

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
const int C = (1<<16) - 10; 
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define mk make_pair
#define pb push_back
#define fr first
#define sc second

vector<vi> edges;

int busca(vector<pii> ord, ll dist, vi s) {
    int l = 0, r = sz(ord)-1;
    
    while(l <= r) {
        int mid = (l+r)/2;

        for(int i = 0; i <= mid; i++) s[ord[i].fr] = 1;
        for(int i = mid+1; i < sz(ord); i++) s[ord[i].fr] = 0;

        int rsp = ask(s);
        if(rsp > dist and l == r) return ord[l].sc;
        if(rsp > dist) r = mid;
        else l = mid+1;
    }

    if(l >= sz(ord)) return -1;
    return ord[l-1].sc;
}

void find_pair(int N, vi U, vi V, int A, int B) {
    int M = sz(U);

    edges.resize(N);

    for(int i = 0; i < M; i++)
        edges[U[i]].pb(i), edges[V[i]].pb(i);
    
    vi ord;
    for(int i = 0; i < N; i++) ord.pb(i);

    sort(all(ord), [](int a, int b){
        if(sz(edges[a]) == sz(edges[b])) return a < b;
        return sz(edges[a]) < sz(edges[b]);
    });

    vi query(M);
    ll dist = ask(query);

    int l = 0, r = N-1;
    while(l < r) {
        int mid = (l+r+1)/2;
        if(r-l >= C) mid = r-C;

        query.clear();
        query.resize(M);
        for(int no = 0; no < mid; no++)
            for(auto ind : edges[ord[no]])
                query[ind] = 1;
                
        if(mid != 0 and ask(query) > dist) r = mid-1;
        else l = mid;
    }
    
    int raiz = ord[l];

    vector<pii> ord_edges;
    vi grupo(N, -1), pai(N), qtd_el(N);
    pii max_grupo = {0,0};

    queue<int> fila;
    fila.push(raiz);
    pai[raiz] = -1;
    grupo[raiz] = raiz;

    while(!fila.empty()) {
        int x = fila.front();
        fila.pop();

        qtd_el[grupo[x]]++;
        max_grupo = max(max_grupo, mk(qtd_el[grupo[x]], grupo[x]));

        if(pai[x] != -1) ord_edges.pb({pai[x],x});
        
        for(auto ind : edges[x]) {
            int viz = U[ind] + V[ind] - x;

            if(ind == pai[x]) continue;
            if(sz(edges[viz]) < sz(edges[raiz])) continue;
            if(sz(edges[viz]) == sz(edges[raiz]) and viz < raiz) continue;

            if(grupo[x] == raiz) grupo[viz] = viz;
            else grupo[viz] = grupo[x];
            pai[viz] = ind;
            fila.push(viz);
        }
    }

    reverse(all(ord_edges));

    vector<pii> o1, o2;
    vi s1(M,1), s2(M,1);

    for(auto [ind, no] : ord_edges) {
        if(grupo[no] != max_grupo.sc) o1.pb({ind, no});
        else s1[ind] = 0;
    }

    int S = busca(o1, dist, s1);
    if(S == -1) S = raiz;

    for(auto [ind, no] : ord_edges) {
        if(grupo[no] != grupo[S]) o2.pb({ind, no});
        else s2[ind] = 0;
    }

    int T = busca(o2, dist, s2);
    if(T == -1) T = raiz;

    answer(S, T);
}

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