Submission #934881

#	Time	Username	Problem	Language	Result	Execution time	Memory
934881		sleepntsheep	Highway Tolls (IOI18_highway)	C++17	0 / 100	15 ms	3516 KiB

highway

#include "highway.h"
#include<bits/stdc++.h>
using namespace std;

int ban[130000],n,m,a,b;std::vector<int>u,v;std::vector<std::pair<int,int>>g[90001];

int sub12(int src,long long need)
{
    vector<int>d(n,1e9),e(n,-1);
    queue<pair<int,int>>q;
    q.emplace(d[src]=src,src);
    while(q.size()){auto[c,u]=q.front();q.pop();for(auto[v,i]:g[u])if(!ban[i]&&d[v]>c+1)q.emplace(d[v]=c+1,v),e[v]=i;}

    vector<int>c;
    for(int i=0;i<n;++i)if(d[i]<1e9)c.push_back(i);

    sort(c.begin(),c.end(),[&d](int i,int v){return d[i]<d[v];});

    int z=0,l=0,r=c.size()-1;
    while(l<=r){
        int y=(l+r)/2;
        vector<int>qq(m,0);
        for(int i=1;i<=y;++i)if(~e[c[i]])qq[e[c[i]]]=1;
        if (ask(qq)==need)z=c[y],r=y-1;
        else l=y+1;
    }
    return z;
}

void sub1234(){
    long long need; {vector<int>qq(m,1); need=ask(qq);}
    auto dt = need / b;
    long long light = dt * a;

    int e1,l=0,r=m-1;
    while(l<=r) {
        int y=(l+r)/2;
        vector<int>qq(m);
        for(int i=0;i<=y;++i)qq[i]=1;
        if(ask(qq)>light)r=y-1,e1=y;
        else l=y+1;
    }


    int p=u[e1],q=v[e1];
    ban[e1]=1;
    int s=sub12(p,b+(dt-1)*a);
    int t=sub12(q,need-b+a);

    answer(s,t);
}

void find_pair(int n_, std::vector<int> u_, std::vector<int> v_, int A_, int B_) {
    n=n_,u=u_,v=v_,a=A_,b=B_;m=u.size();
    for(int i=0;i<m;++i)g[u[i]].push_back({v[i],i}),g[v[i]].push_back({u[i],i});

    sub1234();

}

Compilation message (stderr)

highway.cpp: In function 'void sub1234()':
highway.cpp:45:15: warning: 'e1' may be used uninitialized in this function [-Wmaybe-uninitialized]
   45 |     int p=u[e1],q=v[e1];
      |               ^

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