Submission #881538

#	Time	Username	Problem	Language	Result	Execution time	Memory
881538		andrei_boaca	Highway Tolls (IOI18_highway)	C++17	7 / 100	168 ms	15824 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],roots[5];
ll dist,AA,BB,d[3][100005];
int where[100005];
vector<pii> muchii[100005];
vector<pii> g;
vector<int> w;
ll memo[100005],calls;
bool inarb[300005],inx[300005];
int IND;
void bfs(int ind)
{
    for(int i=0;i<n;i++)
        d[ind][i]=1e9;
    d[ind][roots[ind]]=0;
    queue<int> coada;
    coada.push(roots[ind]);
    while(!coada.empty())
    {
        int nod=coada.front();
        coada.pop();
        for(auto i:muchii[nod])
            if(d[ind][i.first]>d[ind][nod]+1)
            {
                d[ind][i.first]=d[ind][nod]+1;
                coada.push(i.first);
            }
    }
}
ll buildniv(ll nivmax,ll ind)
{
    for(int i=0;i<m;i++)
    {
        if(inarb[i]==0)
        {
            w[i]=1;
            continue;
        }
        int a=g[i].first,b=g[i].second;
        if(max(d[ind][a],d[ind][b])<=nivmax)
            w[i]=0;
        else
            w[i]=1;
    }
    return ask(w);
}
ll buildx(int ind)
{
    for(int i=0;i<m;i++)
    {
        if(inarb[i]==0)
        {
            w[i]=1;
            continue;
        }
        int a=g[i].first,b=g[i].second;
        if(d[ind][a]<d[ind][b])
            swap(a,b);
        if(inx[a])
            w[i]=0;
        else
            w[i]=1;
    }
    return ask(w);
}
bool byniv(int i,int j)
{
    int a=max(d[IND][g[i].first],d[IND][g[i].second]);
    int b=max(d[IND][g[j].first],d[IND][g[j].second]);
    return a<b;
}
int plsfind(int ind)
{
    IND=ind;
    for(int i=0;i<m;i++)
    {
        inarb[i]=0;
        w[i]=0;
    }
    for(int i=0;i<n;i++)
        d[ind][i]=1e9;
    ll nivmax=0;
    d[ind][roots[ind]]=0;
    queue<int> coada;
    coada.push(roots[ind]);
    vector<int> edges;
    while(!coada.empty())
    {
        int nod=coada.front();
        nivmax=max(nivmax,d[ind][nod]);
        coada.pop();
        for(auto i:muchii[nod])
        {
            if(where[i.first]==ind)
            {
                if(d[ind][i.first]>d[ind][nod]+1)
                {
                    d[ind][i.first]=d[ind][nod]+1;
                    inarb[i.second]=1;
                    edges.push_back(i.second);
                    coada.push(i.first);
                }
                else if(d[ind][i.first]==d[ind][nod]+1)
                    w[i.second]=1;
            }
            else if(i.first!=roots[3-ind])
                w[i.second]=1;
        }
    }
    //sort(edges.begin(),edges.end(),byniv);
    /*ll val=ask(w);
    if(val==dist*BB)
        return roots[ind];*/
    ll st=0;
    ll dr=edges.size();
    dr--;
    ll ans=-1;
    int poz=0;
    while(st<=dr)
    {
        ll mij=(st+dr)/2;
        for(int i:edges)
            w[i]=1;
        for(int j=0;j<=mij;j++)
            w[edges[j]]=0;
        ll x=ask(w);
        int p=edges[mij];
        int a=g[p].first;
        int b=g[p].second;
        if(x!=dist*AA)
            st=mij+1;
        else
        {
            poz=mij;
            if(d[ind][a]<d[ind][b])
                swap(a,b);
            ans=a;
            dr=mij-1;
        }
    }
    if(ans==-1)
        return roots[ind];
    return ans;
}
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);
    dist=ask(w)/A;
    ll st=0;
    ll dr=m-1;
    while(st<=dr)
    {
        ll mij=(st+dr)/2;
        for(int i=0;i<m;i++)
        {
            if(i<=mij)
                w[i]=1;
            else
                w[i]=0;
        }
        ll val=ask(w);
        if(val>dist*A)
        {
            roots[1]=g[mij].first;
            roots[2]=g[mij].second;
            dr=mij-1;
        }
        else
            st=mij+1;
    }
    bfs(1);
    bfs(2);
    for(int i=0;i<n;i++)
    {
        if(d[1][i]<d[2][i])
            where[i]=1;
        if(d[2][i]<d[1][i])
            where[i]=2;
    }
    int S=plsfind(1);
    int T=plsfind(2);
    answer(S,T);
}

Compilation message (stderr)

highway.cpp: In function 'int plsfind(int)':
highway.cpp:124:9: warning: variable 'poz' set but not used [-Wunused-but-set-variable]
  124 |     int poz=0;
      |         ^~~

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