Submission #880630

#	Time	Username	Problem	Language	Result	Execution time	Memory
880630		andrei_boaca	Highway Tolls (IOI18_highway)	C++17	0 / 100	725 ms	262144 KiB

highway

#include "highway.h"
#include <bits/stdc++.h>
//#include "grader.cpp"
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
mt19937 rng(chrono::steady_clock().now().time_since_epoch().count());
int n,m,niv[100005],par[100005],topar[100005],dp[21][100005],in[100005],out[100005],timp;
ll dist,AA,BB;
vector<pii> muchii[100005];
vector<pii> g;
vector<int> w;
ll memo[100005],calls;
bool isancestor(int a,int b)
{
    return in[a]<=in[b]&&out[a]>=out[b];
}
int LCA(int a,int b)
{
    if(niv[a]>niv[b])
        swap(a,b);
    if(isancestor(a,b))
        return a;
    for(int i=20;i>=0;i--)
        if(dp[i][a]!=-1&&!isancestor(dp[i][a],b))
            a=dp[i][a];
    return par[a];
}
void dfs(int nod)
{
    timp++;
    in[nod]=timp;
    dp[0][nod]=par[nod];
    for(int i=1;i<=20;i++)
    {
        if(dp[i-1][nod]==-1)
        {
            dp[i][nod]=-1;
            continue;
        }
        dp[i][nod]=dp[i-1][dp[i-1][nod]];
    }
    for(auto i:muchii[nod])
        if(i.first!=par[nod])
        {
            par[i.first]=nod;
            niv[i.first]=niv[nod]+1;
            topar[i.first]=i.second;
            dfs(i.first);
        }
    out[nod]=timp;
}
ll buildniv(int p)
{
    if(memo[p]!=0)
        return memo[p];
    for(int i=0;i<m;i++)
    {
        w[i]=1;
        if(min(niv[g[i].first],niv[g[i].second])<=p)
            w[i]=0;
    }
    calls++;
    assert(calls<=60);
    memo[p]=ask(w);
    return memo[p];
}
int getnode(vector<int> cand)
{
    while(true)
    {
        if(cand.size()==1)
            return cand[0];
        vector<int> x,y;
        int lg=cand.size();
        for(int i=0;i<cand.size();i++)
        {
            if(i<lg/2)
                x.push_back(cand[i]);
            else
                y.push_back(cand[i]);
        }
        for(int i=0;i<m;i++)
            w[i]=1;
        for(int i:x)
            w[topar[i]]=0;
        calls++;
        assert(calls<=60);
        ll val=ask(w);
        if(val<dist*BB)
            cand=x;
        else
            cand=y;
    }
    return -1;
}
int where[100005];
int makesets()
{
    for(int i=0;i<m;i++)
    {
        int a=g[i].first;
        int b=g[i].second;
        if(where[a]==where[b])
            w[i]=1;
        else
            w[i]=0;
    }
    return ask(w);
}
void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B)
{
    AA=A;
    BB=B;
    n=N;
    m=U.size();
    for(int i=0;i<m;i++)
    {
        int a=U[i],b=V[i];
        g.push_back({a,b});
        muchii[a].push_back({b,i});
        muchii[b].push_back({a,i});
    }
    w.resize(m);
    /*if(A==1&&B==2)
    {
        int xx=0;
        for(int bit=0;bit<17;bit++)
        {
            for(int i=0;i<n;i++)
            {
                if((i>>bit)&1)
                    where[i]=0;
                else
                    where[i]=1;
            }
            int d=makesets();
            if(d%2==1)
                xx^=(1<<bit);
        }
        vector<pii> vv;
        for(int a=0;a<n;a++)
        {
            int b=(a^xx);
            if(b>a)
                vv.push_back({a,b});
        }
        int st=0;
        int dr=vv.size()-1;
        int S=0,T=0;
        while(st<=dr)
        {
            int mij=(st+dr)/2;
            for(int i=0;i<vv.size();i++)
            {
                int a=vv[i].first;
                int b=vv[i].second;
                if(i<=mij)
                {
                    where[a]=0;
                    where[b]=1;
                }
                else
                {
                    where[a]=0;
                    where[b]=0;
                }
            }
            int d=makesets();
            if(d%2==1)
            {
                S=vv[mij].first;
                T=vv[mij].second;
                dr=mij-1;
            }
            else
                st=mij+1;
        }
        answer(S,T);
        return;
    }*/
    for(int i=0;i<n;i++)
        par[i]=-1;
    int root=rng()%n;
    niv[root]=1;
    dfs(root);
    int nivmax=0;
    for(int i=0;i<n;i++)
        nivmax=max(nivmax,niv[i]);
    for(int i=0;i<m;i++)
        w.push_back(0);
    calls++;
    assert(calls<=60);
    dist=ask(w)/A;
    int nivlca=nivmax;
    int st=1;
    int dr=nivmax-1;
    while(st<=dr)
    {
        int mij=(st+dr)/2;
        ll val=buildniv(mij);
        if(val<dist*B)
        {
            nivlca=mij;
            dr=mij-1;
        }
        else
            st=mij+1;
    }
    int nivS=nivlca;
    int nivT=0;
    st=nivlca;
    dr=nivmax-1;
    while(st<=dr)
    {
        int mij=(st+dr)/2;
        ll val=buildniv(mij);
        if(val==dist*A)
        {
            nivT=mij+1;
            dr=mij-1;
        }
        else
            st=mij+1;
    }
    nivS=nivlca+(dist-(nivT-nivlca));
    //assert(nivS<=nivT);
    vector<int> c1,c2;
    for(int i=0;i<n;i++)
    {
        if(niv[i]==nivS)
            c1.push_back(i);
        if(niv[i]==nivT)
            c2.push_back(i);
    }
    int T=getnode(c2);
    c1.clear();
    for(int i=0;i<n;i++)
        if(niv[i]==nivS&&niv[LCA(i,T)]==nivlca)
            c1.push_back(i);
    int S=getnode(c1);
    //assert(S!=T);
    //assert(S!=-1&&T!=-1);
    answer(S,T);
}

Compilation message (stderr)

highway.cpp: In function 'int getnode(std::vector<int>)':
highway.cpp:76:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |         for(int i=0;i<cand.size();i++)
      |                     ~^~~~~~~~~~~~

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