Submission #235866

#	Time	Username	Problem	Language	Result	Execution time	Memory
235866		laoriu	Highway Tolls (IOI18_highway)	C++14	0 / 100	24 ms	16000 KiB

highway

#include <bits/stdc++.h>
#include "highway.h"

using namespace std;
typedef pair <int,int> pp;
int n,m,l,vs[200002],D[2][200002];
vector <pp> P[200002],adj[200002],A[200002];
pp B[200002];
vector <int> ds,sub[2],w;
int ss,tt,aa,bb;

void build_tree(int x,int u,int v)
{
    memset(vs,0,sizeof(vs));
    queue <int> q;
    adj[u].push_back({v,x});adj[v].push_back({u,x});
    q.push(u);q.push(v);vs[u]=vs[v]=1;ds.push_back(x);
    while (!q.empty())
    {
        int u=q.front();
        q.pop();
        for (int i=0;i<A[u].size();i++)
        {
            int v=A[u][i].first;
            int x=A[u][i].second;
            if (vs[v]==1) continue;
            adj[u].push_back({v,x});
            vs[v]=1;
            ds.push_back(x);
        }
    }
    //for (int i=0;i<ds.size();i++)
    //    cout<<ds[i]<<' ';cout<<endl;
}
void bfs(int p,int u,int ban)
{
    queue <int> q;
    for (int i=0;i<n;i++)
        D[p][i]=1e9;
    memset(vs,0,sizeof(vs));
    q.push(u);D[p][u]=0;vs[u]=1;
    while (!q.empty())
    {
        int u=q.front();
        q.pop();
        for (int i=0;i<adj[u].size();i++)
        {
            int v=adj[u][i].first;
            int x=adj[u][i].second;
            if (vs[v]==1||x==ban) continue;
            vs[v]=1;D[p][v]=D[p][u]+1;
            sub[p].push_back(x);
        }
    }
}
int find1(int p,int s,int l)
{
    if (l==0) return s;
    vector <int> X;
    for (int i=0;i<sub[p].size();i++)
    {
        int u=B[sub[p][i]].first;
        int v=B[sub[p][i]].second;
        if (D[p][u]>D[p][v]) swap(u,v);
        if (D[p][u]==l-1&&D[p][v]==l)
        {
            X.push_back(sub[p][i]);
        }
    }
    int d=0;int c=X.size()-1;
    vector <int> w;w.resize(m,0);
    int ans=0;
    while (d<=c)
    {
        int mid=(d+c)/2;
        for (int i=0;i<m;i++)
            w[i]=1;
        for (int i=0;i<=mid;i++)
            w[X[i]]=0;
        if (ask(w)<(long long)bb*l)
        {
            c=mid-1;
            ans=X[mid];
        }
        else d=mid+1;
    }
    int u=B[ans].first;int v=B[ans].second;
    if (D[p][u]==l) return u;else return v;
}
void find_pair(int n,vector <int> U,vector <int> V,int a,int b)
{
    aa=a;bb=b;
    m=U.size();
    for (int i=0;i<U.size();i++)
    {
        A[U[i]].push_back({V[i],i});
        A[V[i]].push_back({U[i],i});
        B[i]={U[i],V[i]};
    }
    w.resize(m,0);
    long long t=ask(w);l=t/a;
    int d=0;int c=m-1;int x;
    while (d<=c)
    {
        int mid=(d+c)/2;
        for (int i=0;i<m;i++)
            if (i<=mid) w[i]=0;else w[i]=1;
        if (ask(w)==t)
        {
            x=mid;
            c=mid-1;
        }
        else d=mid+1;
    }
    int u=U[x];int v=V[x];
    //cout<<x<<endl;

    build_tree(x,u,v);
    bfs(0,u,x);bfs(1,v,x);
    for (int i=0;i<m;i++) w[i]=1;
    for (int i=0;i<sub[0].size();i++)
        w[sub[0][i]]=0;
    int l1;
    t=ask(w);
    for (int i=0;i<=l-1;i++)
        if ((long long) a*i+(long long) b*(l-i)==t) l1=i;
    int l2=l-1-l1;
    //cout<<l1<<' '<<l2<<endl;
    answer(find1(0,u,l1),find1(1,v,l2));
}

Compilation message (stderr)

highway.cpp: In function 'void build_tree(int, int, int)':
highway.cpp:22:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i=0;i<A[u].size();i++)
                      ~^~~~~~~~~~~~
highway.cpp: In function 'void bfs(int, int, int)':
highway.cpp:46:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i=0;i<adj[u].size();i++)
                      ~^~~~~~~~~~~~~~
highway.cpp: In function 'int find1(int, int, int)':
highway.cpp:60:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0;i<sub[p].size();i++)
                  ~^~~~~~~~~~~~~~
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:94:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0;i<U.size();i++)
                  ~^~~~~~~~~
highway.cpp:121:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0;i<sub[0].size();i++)
                  ~^~~~~~~~~~~~~~
highway.cpp:129:11: warning: 'l1' may be used uninitialized in this function [-Wmaybe-uninitialized]
     answer(find1(0,u,l1),find1(1,v,l2));
     ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
highway.cpp:115:14: warning: 'x' may be used uninitialized in this function [-Wmaybe-uninitialized]
     int u=U[x];int v=V[x];
              ^

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