Submission #124612

#	Time	Username	Problem	Language	Result	Execution time	Memory
124612		forelax	Highway Tolls (IOI18_highway)	C++14	100 / 100	558 ms	29852 KiB

highway

#include "highway.h"
#include<bits/stdc++.h>
using namespace std;
/*
int N,M,A,B,S,T;
vector<int> U,V;
vector<vector<pair<int,int> > > NG;
long long int ask(vector<int> W){
    queue<pair<long long int,int> > q;
    q.push({0,S});
    vector<long long int> dst(N,1e16);
    dst[S]=0;
    while(q.size()){
        pair<int,int> cur=q.front();
        long long int d=-cur.first;
        long long int nd=cur.second;
        q.pop();
        for(int i = 0 ; i < NG[nd].size() ; i ++){
            int ne=NG[nd][i].first;
            int ew=NG[nd][i].second;
            ew=W[ew]*(B-A)+A;
            if(d+ew<dst[ne]){
                dst[ne]=d+ew;
                q.push({-dst[ne],ne});
            }
        }
    }
    return dst[T];
}
void answer(int A,int B){
    if(min(A,B)!=min(S,T)||max(A,B)!=max(S,T))cout<<"WONG"<<endl;
    cout<<S<<" "<<T<<" "<<A<<" "<<B<<endl;
}
*/



int n,m,a,b,s,t;
long long int minpr,maxpr,tmp;
vector<int> u,v,w;
vector<vector<pair<int,int> > > ng;
vector<vector<int> > bfs(int st,int ed){
    vector<vector<int> > rz(n,{n+1,0,0});
    rz[st]={0,ed,st};
    priority_queue<vector<int> > q;
    q.push({rz[st]});
    while(q.size()){
        vector<int> cr=q.top();
        q.pop();
        int cn=cr[2];
        int cd=-cr[0];
        for(int i = 0 ; i < ng[cn].size() ; i ++ ){
            int ne=ng[cn][i].first;
            int en=ng[cn][i].second;
            if(rz[ne][0]>cd+1){
                rz[ne]={-cd-1,en,ne};
                q.push(rz[ne]);
                rz[ne][0]*=-1;
            }
        }
    }
    return rz;
}
int fnd(vector<vector<int> > s0,vector<vector<int> > s3){
    int l=0,r=s0.size();
    while(l!=r-1){
        int md=(l+r)/2;
        w.clear();
        w.resize(m,1);
        for(int i = 0 ; i < s3.size() ; i ++)
            w[s3[i][1]]=0;
        w[s0[0][1]]=1;
        for(int i = 0 ; i < md ; i ++)
            w[s0[i][1]]=0;
        tmp=ask(w);
        if(tmp==minpr){
            r=md;
        }else{
            l=md;
        }
    }
    return s0[l][2];
}
void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
    u=U;v=V;n=N;
    m=u.size();
    ng.clear();
    ng.resize(n);
    for(int i = 0 ; i < m ; i ++){
        ng[u[i]].push_back({v[i],i});
        ng[v[i]].push_back({u[i],i});
    }
    w.clear();
    w.resize(m);
    minpr=ask(w);
    maxpr=minpr/A*B;
    int l=0,r=m;
    while(l!=r-1){
        int md=(l+r)/2;
        for(int i = 0 ; i < m ; i ++){
            if(i<md)
                w[i]=1;
            else
                w[i]=0;
        }
        tmp=ask(w);
        if(tmp==minpr){
            l=md;
        }else{
            r=md;
        }
    }
//    cout<<l<<" "<<u[l]<<" "<<v[l]<<endl<<endl;
    vector<vector<int> > g1=bfs(u[l],l);
    vector<vector<int> > g2=bfs(v[l],l);
    vector<vector<int> > s1,s2;
    for(int i = 0 ; i < n ; i ++){
        if(g1[i][0]<g2[i][0]){
            s1.push_back(g1[i]);
        }else if(g2[i][0]<g1[i][0]){
            s2.push_back(g2[i]);
        }
    }
    sort(s1.begin(),s1.end());
    sort(s2.begin(),s2.end());
//    for(int i = 0 ; i < s1.size() ; i ++){
//        cout<<s1[i][0]<<" "<<s1[i][1]<<" "<<s1[i][2]<<endl;
//    }
//    cout<<endl;
    t=fnd(s1,s2);
//    cout<<endl;
//    cout<<endl;
//    for(int i = 0 ; i < s2.size() ; i ++){
//        cout<<s2[i][0]<<" "<<s2[i][1]<<" "<<s2[i][2]<<endl;
//    }
//    cout<<endl;
//    cout<<endl;
    s=fnd(s2,s1);
    answer(s,t);
}

//int main(){
//    cin>>N>>M>>A>>B>>S>>T;
//    U.resize(M);
//    V.resize(M);
//    NG.resize(N);
//    for(int i = 0 ; i < M ; i ++){
//        cin>>U[i]>>V[i];
//        NG[U[i]].push_back({V[i],i});
//        NG[V[i]].push_back({U[i],i});
//    }
//    cout<<"EVEIL"<<endl;
//    find_pair(N,U,V,A,B);
//    /*for(S = 0 ; S < N ; S ++){
//        for(T = 0 ; T < N ; T ++){
//            if(S==T)continue;
//            find_pair(N,U,V,A,B);
//
//        }
//    }*/
//}



/**

14 22 14862 18232 6 10
0 1 0 4 0 13 0 9 0 10
1 13 1 2 1 4
2 3 2 5 2 6
3 6 3 7
4 5 4 8
5 8 5 9
8 10 8 12
9 12
10 11
11 12


**/

/**

10 9 2 3 4 8
0 1
0 2
0 3
0 4
0 5
0 6
0 7
0 8
0 9

**/

/**


10 10 2 3 0 5
0 1
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 0

**/

Compilation message (stderr)

highway.cpp: In function 'std::vector<std::vector<int> > bfs(int, int)':
highway.cpp:52:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = 0 ; i < ng[cn].size() ; i ++ ){
                         ~~^~~~~~~~~~~~~~~
highway.cpp: In function 'int fnd(std::vector<std::vector<int> >, std::vector<std::vector<int> >)':
highway.cpp:70:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = 0 ; i < s3.size() ; i ++)
                         ~~^~~~~~~~~~~

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