제출 #711266

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
711266		rrrr10000	통행료 (IOI18_highway)	C++14	51 / 100	363 ms	262148 KiB

highway

#include <bits/stdc++.h>
#include "highway.h"
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef pair<ll,ll> P;
typedef tuple<ll,ll,ll> PP;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<bool> vb;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define REP(i,k,n) for(ll i=(ll)(k);i<(ll)(n);i++)
#define all(a) a.begin(),a.end()
#define fi first
#define se second
#define pb emplace_back
#define rsort(a) {sort(all(a));reverse(all(a));}
template<class T> void out(T a){cout<<a<<endl;}
template<class T> void outv(T v){rep(i,v.size()){if(i)cout<<' ';cout<<v[i];}cout<<endl;}
template<class T> void outvv(T v){for(auto x:v)outv(x);}
template<class T> void outvp(T v){rep(i,v.size()){cout<<'('<<v[i].fi<<','<<v[i].se<<')';}cout<<endl;}
template<class T> void outvvp(T v){for(auto x:v)outvp(x);}
template<class T> bool chmin(T&a,T b){if(a>b){a=b;return true;}return false;}

void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B){
    ll M=U.size();
    vvp g(N);
    rep(i,M){
        g[U[i]].pb(V[i],i);
        g[V[i]].pb(U[i],i);
    }
    vector<int> tmp(M);
    ll dis=ask(tmp)/A;
    vb dead(N,false);
    ll rt=0;
    vi sub(N),dep(N),par(N);
    while(true){
        vi al;
        auto dfs=[&](auto && self,ll i,ll p,ll d) -> void {
            al.pb(i);
            sub[i]=1;dep[i]=d;
            for(auto x:g[i])if(x.fi!=p&&!dead[x.fi]){
                par[x.fi]=x.se;
                self(self,x.fi,i,d+1);
                sub[i]+=sub[x.fi];
            }
        };dfs(dfs,rt,-1,0);
        if(al.size()==2){
            answer(al[0],al[1]);
            return;
        }
        ll sz=sub[rt];
        auto find_cen=[&](auto && self,ll i,ll p) -> ll {
            for(auto x:g[i])if(x.fi!=p&&!dead[x.fi]&&sub[x.fi]*2>sz)return self(self,x.fi,i);
            return i;
        };
        rt=find_cen(find_cen,rt,-1);
        dfs(dfs,rt,-1,0);
        vp srt;
        for(auto x:g[rt])if(!dead[x.fi])srt.pb(sub[x.fi],x.fi);
        rsort(srt);
        vi a,b;
        ll cnta=0,cntb=0;
        for(auto x:srt){
            if(cnta<cntb){
                swap(cnta,cntb);swap(a,b);
            }
            cntb+=x.fi;
            b.pb(x.se);
        }
        vi color(N,-1);
        auto dfs2=[&](auto && self,ll i,ll p,ll c) -> void {
            color[i]=c;
            for(auto x:g[i])if(x.fi!=p&&!dead[x.fi])self(self,x.fi,i,c);
        };
        for(ll x:a)dfs2(dfs2,x,rt,0);
        for(ll x:b)dfs2(dfs2,x,rt,1);
        rep(i,M)tmp[i]=0;
        rep(i,M)if((color[U[i]]==0||color[V[i]]==0)&&!dead[U[i]]&&!dead[V[i]])tmp[i]=1;
        ll res=ask(tmp);
        if(res==dis*A){
            for(auto x:a)dead[x]=true;
        }
        else if(res==dis*B){
            for(auto x:b)dead[x]=true;
        }
        else{
            ll lena=(res-dis*A)/(B-A),lenb=dis-lena;
            vi a,b;
            rep(i,N)if(dep[i]==lena&&color[i]==0)a.pb(i);
            rep(i,N)if(dep[i]==lenb&&color[i]==1)b.pb(i);
            while(a.size()>1){
                vi l,r;
                rep(i,a.size()/2)l.pb(a[i]);
                REP(i,a.size()/2,a.size())r.pb(a[i]);
                rep(i,M)tmp[i]=0;
                for(ll x:l)tmp[par[x]]=1;
                if(ask(tmp)==dis*A)a=r;
                else a=l;
            }
            while(b.size()>1){
                vi l,r;
                rep(i,b.size()/2)l.pb(b[i]);
                REP(i,b.size()/2,b.size())r.pb(b[i]);
                rep(i,M)tmp[i]=0;
                for(ll x:l)tmp[par[x]]=1;
                if(ask(tmp)==dis*A)b=r;
                else b=l;
            }
            answer(a[0],b[0]);return;
        }
    }
}

long long ask(const std::vector<int> &w);
void answer(int s, int t);

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