Submission #966565

#	Time	Username	Problem	Language	Result	Execution time	Memory
966565		Warinchai	Highway Tolls (IOI18_highway)	C++14	51 / 100	154 ms	18848 KiB

highway

#include "highway.h"
#include<bits/stdc++.h>
using namespace std;
vector<pair<int,int>>adj[100000];
int vis[100000];
void dfs(int u,vector<int>&x,vector<int>&nodes,int p,int val){
    //cerr<<u<<"\n";
    vis[u]=1;
    x.push_back(val);
    nodes.push_back(u);
    for(auto v:adj[u])if(!vis[v.first])dfs(v.first,x,nodes,u,v.second);
}
pair<int,pair<int,int> > dis1[100000],dis2[100000];
int to1[100000],to2[100000];
void subgraph(int n,vector<int>u,vector<int>v,int a,int b,long long cost){
    //cerr<<"work\n";
    int st=0,en=u.size()-1,ans=0;
    while(st<=en){
        int m=(st+en)/2;
        //cerr<<"m:"<<m<<"  ";
        vector<int>temp;
        for(int i=0;i<=m;i++)temp.push_back(1);
        for(int i=m+1;i<u.size();i++)temp.push_back(0);
      //  cerr<<temp.size()<<"\n";
        long long tcost=ask(temp);
        //cerr<<tcost<<"\n";
        if(tcost>cost){
            en=m-1;
            ans=m;
        }else{
            st=m+1;
        }
    }
    //cerr<<"work\n";
    int bg=u[ans];
    int ed=v[ans];
    //cerr<<bg<<" "<<ed<<"\n";
    queue<pair<int,int> >q;
    q.push({bg,0});
    dis1[bg].second.first=dis2[bg].second.first=ans;
    //cerr<<"dis1:\n";
    for(int i=0;i<n;i++)vis[i]=0;
    while(!q.empty()){
        int x=q.front().first;
        int lv=q.front().second;
        q.pop();
        //if(vis[x])continue;
        ///cerr<<x<<" "<<lv<<"\n";
        //vis[x]=1;
        dis1[x].first=lv;
        for(auto z:adj[x])if(!dis1[z.first].first&&z.first!=bg&&!vis[z.first])vis[z.first]=1,q.push({z.first,lv+1}),dis1[z.first].second.first=z.second,dis1[z.first].second.second=x;
    }
    for(int i=0;i<n;i++)vis[i]=0;
    q.push({ed,0});
    //cerr<<"dis2:\n";
    while(!q.empty()){
        int x=q.front().first;
        int lv=q.front().second;
        q.pop();
        //if(vis[x])continue;
        //cerr<<x<<" "<<lv<<"\n";
        //vis[x]=1;
        dis2[x].first=lv;
        for(auto z:adj[x])if(!dis2[z.first].first&&z.first!=ed&&!vis[z.first])vis[z.first]=1,q.push({z.first,lv+1}),dis2[z.first].second.first=z.second,dis2[z.first].second.second=x;
    }
    //for(int i=0;i<n;i++)cerr<<i<<" "<<dis1[i].first<<" "<<dis2[i].first<<"\n";
    vector<int>temp;
    vector<int>side1;
    vector<int>side2;
    vector<int>node1;
    vector<int>node2;
    for(int i=0;i<n;i++)adj[i].clear();
    for(int i=0;i<n;i++){
        if(i==bg||i==ed)continue;
        //cerr<<i<<":"<<dis1[i].first<<" "<<dis2[i].first<<"\n";
        if(dis1[i].first<dis2[i].first){
            adj[dis1[i].second.second].push_back({i,dis1[i].second.first});
            //cerr<<dis1[i].second.second<<"\n";
        }else{
            adj[dis2[i].second.second].push_back({i,dis2[i].second.first});
            //cerr<<dis2[i].second.second<<"\n";
        }
    }
    /*for(int i=0;i<n;i++){
        cerr<<i<<":\n";
        for(auto x:adj[i])cerr<<x.first<<" ";
        cerr<<"\n";
    }*/
    for(int i=0;i<u.size();i++)temp.push_back(0);
    //temp[ans]=1;
    //assert(ask(temp)>cost);
    //cerr<<"dfs1:\n";
    for(int i=0;i<n;i++)vis[i]=0;
    dfs(bg,side1,node1,ed,ans);
    for(int i=0;i<n;i++)vis[i]=0;
    //cerr<<"dfs2:\n";
    dfs(ed,side2,node2,bg,ans);
    for(int i=0;i<u.size();i++)temp[i]=1;
    long long cost1=ask(temp);
    long long cost2=ask(temp);
    int n1,n2;
    for(int i=0;i<u.size();i++)temp[i]=1;
    for(auto x:side1)temp[x]=0;
    //cerr<<"pass\n";
    //cerr<<"side1:\n";
    /*for(auto x:side1)cerr<<x<<" ";
    cerr<<"\n";
    cerr<<"side2:\n";
    for(auto x:side2)cerr<<x<<" ";
    cerr<<"\n";*/
    st=0,en=side1.size()-1;
    while(st<=en){
        int m=(st+en)/2;
        for(int i=0;i<=m;i++)temp[side1[i]]=1;
        if(ask(temp)>=cost1){
            en=m-1;
            n1=m;
        }else{
            st=m+1;
        }
        for(int i=0;i<=m;i++)temp[side1[i]]=0;
    }
    for(int i=0;i<u.size();i++)temp[i]=1;
    for(auto x:side2)temp[x]=0;
    st=0,en=side2.size()-1;
    while(st<=en){
        int m=(st+en)/2;
        for(int i=0;i<=m;i++)temp[side2[i]]=1;
        if(ask(temp)>=cost2){
            en=m-1;
            n2=m;
        }else{
            st=m+1;
        }
        for(int i=0;i<=m;i++)temp[side2[i]]=0;
    }
    //cerr<<node1[n1]<<" "<<node2[n2]<<"\n";
    answer(node1[n1],node2[n2]);
}
void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
    //cerr<<"work\n";
    for(int i=0;i<U.size();i++){
        adj[U[i]].push_back({V[i],i});
        adj[V[i]].push_back({U[i],i});
    }
    vector<int>temp;
    for(int i=0;i<U.size();i++)temp.push_back(0);
    //if(U.size()!=N-1)return answer(rand()%N,rand()%N);
    subgraph(N,U,V,A,B,ask(temp));
}

Compilation message (stderr)

highway.cpp: In function 'void subgraph(int, std::vector<int>, std::vector<int>, int, int, long long int)':
highway.cpp:23:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |         for(int i=m+1;i<u.size();i++)temp.push_back(0);
      |                       ~^~~~~~~~~
highway.cpp:89:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |     for(int i=0;i<u.size();i++)temp.push_back(0);
      |                 ~^~~~~~~~~
highway.cpp:98:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |     for(int i=0;i<u.size();i++)temp[i]=1;
      |                 ~^~~~~~~~~
highway.cpp:102:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |     for(int i=0;i<u.size();i++)temp[i]=1;
      |                 ~^~~~~~~~~
highway.cpp:123:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  123 |     for(int i=0;i<u.size();i++)temp[i]=1;
      |                 ~^~~~~~~~~
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:142:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  142 |     for(int i=0;i<U.size();i++){
      |                 ~^~~~~~~~~
highway.cpp:147:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  147 |     for(int i=0;i<U.size();i++)temp.push_back(0);
      |                 ~^~~~~~~~~
highway.cpp: In function 'void subgraph(int, std::vector<int>, std::vector<int>, int, int, long long int)':
highway.cpp:138:30: warning: 'n2' may be used uninitialized in this function [-Wmaybe-uninitialized]
  138 |     answer(node1[n1],node2[n2]);
      |                              ^
highway.cpp:138:20: warning: 'n1' may be used uninitialized in this function [-Wmaybe-uninitialized]
  138 |     answer(node1[n1],node2[n2]);
      |                    ^

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