Submission #1068115

#	Time	Username	Problem	Language	Result	Execution time	Memory
1068115		Sir_Ahmed_Imran	Highway Tolls (IOI18_highway)	C++17	18 / 100	114 ms	20172 KiB

highway

                            ///~~~LOTA~~~///
#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define append push_back
#define add insert
#define nl '\n'
#define ff first
#define ss second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define all(x) (x).begin(),(x).end()
#define L0TA ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define terminator main
#define N 90000
int d;
int ve[N];
int par[N];
int dept[N];
vector<pii> e[N];
vector<int> x[N];
void dfs(int v,int u){
    d=max(d,dept[v]);
    x[dept[v]].append(v);
    for(auto& i:e[v]){
        if(i.ff==u)
            continue;
        dept[i.ff]=dept[v]+1;
        ve[i.ff]=i.ss;
        par[i.ff]=v;
        dfs(i.ff,v);
    }
}
void find_pair(int n,vector<int> v,vector<int> u,int a,int b){
    ll m,o,p,q,r,s,t;
    vector<int> h;
    for(int i=1;i<n;i++)
        h.append(0);
    for(int i=m=d=0;i<n-1;i++){
        e[v[i]].append({u[i],i});
        e[u[i]].append({v[i],i});
    }
    o=ask(h);
    dfs(0,-1);
    for(int i=65536;i>0;i/=2){
        if(m+i>d) continue;
        for(int j=1;j<=m+i;j++)
            for(auto& k:x[j])
                h[ve[k]]=1;
        r=ask(h);
        for(int j=1;j<=m+i;j++)
            for(auto& k:x[j])
                h[ve[k]]=0;
        if(r==o) m+=i;
    }
    p=q=m;
    for(int i=65536;i>0;i/=2){
        if(p+i<=d){
            for(auto& j:x[p+i])
                h[ve[j]]=1;
            r=ask(h);
            for(auto& j:x[p+i])
                h[ve[j]]=0;
            if(r-o==2*(b-a)) p+=i;
        }
        if(q+i<=d){
            for(auto& j:x[q+i])
                h[ve[j]]=1;
            r=ask(h);
            for(auto& j:x[q+i])
                h[ve[j]]=0;
            if(r>o) q+=i;
        }
    }
    s=t=0;
    for(int i=65536;i>0;i/=2){
        if(s+i>x[q].size())
            continue;
        for(int j=0;j<s+i;j++)
            h[ve[x[q][j]]]=1;
        r=ask(h);
        for(int j=0;j<s+i;j++)
            h[ve[x[q][j]]]=0;
        if(r==o) s+=i;
    }
    s=q=x[q][s];
    while(dept[q]>p)
        q=par[q];
    if(p==m){
        answer(s,q);
        return;
    }
    for(int i=65536;i>0;i/=2){
        if(t+i>x[p].size())
            continue;
        for(int j=0;j<t+i;j++)
            h[ve[x[p][j]]]=1;
        h[ve[q]]=0;
        r=ask(h);
        for(int j=0;j<t+i;j++)
            h[ve[x[p][j]]]=0;
        if(r==o) t+=i;
    }
    t=x[p][t];
    answer(s,t);
}

Compilation message (stderr)

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:79:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |         if(s+i>x[q].size())
      |            ~~~^~~~~~~~~~~~
highway.cpp:96:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |         if(t+i>x[p].size())
      |            ~~~^~~~~~~~~~~~

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