oj.uz

Submission #711266

# Submission time Handle Problem Language Result Execution time Memory
711266 2023-03-16T12:02:20 Z rrrr10000 Highway Tolls (IOI18_highway) C++14
51 / 100
 363 ms 262148 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 312 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 1 ms 208 KB Output is correct
4 Correct 1 ms 208 KB Output is correct
5 Correct 1 ms 208 KB Output is correct
6 Correct 1 ms 208 KB Output is correct
7 Correct 1 ms 208 KB Output is correct
8 Correct 1 ms 208 KB Output is correct
9 Correct 1 ms 208 KB Output is correct
10 Correct 1 ms 208 KB Output is correct
11 Correct 1 ms 208 KB Output is correct
12 Correct 1 ms 208 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 12 ms 1872 KB Output is correct
3 Correct 166 ms 13008 KB Output is correct
4 Correct 161 ms 13240 KB Output is correct
5 Correct 158 ms 13008 KB Output is correct
6 Correct 144 ms 13156 KB Output is correct
7 Correct 109 ms 13220 KB Output is correct
8 Correct 144 ms 13012 KB Output is correct
9 Correct 117 ms 13204 KB Output is correct
10 Correct 180 ms 13072 KB Output is correct
11 Correct 158 ms 14096 KB Output is correct
12 Correct 194 ms 14676 KB Output is correct
13 Correct 150 ms 14232 KB Output is correct
14 Correct 168 ms 13880 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 2212 KB Output is correct
2 Correct 17 ms 4152 KB Output is correct
3 Correct 29 ms 5796 KB Output is correct
4 Correct 76 ms 16908 KB Output is correct
5 Correct 91 ms 16852 KB Output is correct
6 Correct 99 ms 16828 KB Output is correct
7 Correct 132 ms 16844 KB Output is correct
8 Correct 120 ms 16844 KB Output is correct
9 Correct 94 ms 16852 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 336 KB Output is correct
2 Correct 11 ms 1768 KB Output is correct
3 Correct 126 ms 10660 KB Output is correct
4 Correct 159 ms 13052 KB Output is correct
5 Correct 145 ms 13076 KB Output is correct
6 Correct 139 ms 13032 KB Output is correct
7 Correct 165 ms 13096 KB Output is correct
8 Correct 144 ms 13068 KB Output is correct
9 Correct 138 ms 13196 KB Output is correct
10 Correct 118 ms 13260 KB Output is correct
11 Correct 158 ms 13840 KB Output is correct
12 Correct 140 ms 14616 KB Output is correct
13 Correct 162 ms 14300 KB Output is correct
14 Correct 164 ms 14624 KB Output is correct
15 Correct 172 ms 13092 KB Output is correct
16 Correct 130 ms 13064 KB Output is correct
17 Correct 156 ms 14380 KB Output is correct
18 Correct 182 ms 14164 KB Output is correct
19 Correct 159 ms 13008 KB Output is correct
20 Correct 200 ms 15048 KB Output is correct
21 Correct 137 ms 15284 KB Output is correct
22 Correct 106 ms 16420 KB Output is correct
23 Correct 123 ms 15292 KB Output is correct
24 Correct 127 ms 14592 KB Output is correct
25 Correct 139 ms 16788 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 363 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Runtime error 341 ms 262148 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -