Submission #124415

#	Time	Username	Problem	Language	Result	Execution time	Memory
124415		forelax	Highway Tolls (IOI18_highway)	C++14	69 / 100	316 ms	11624 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){
    cout<<A<<" "<<B<<endl;
}**/

int n,m,a,b,s,t;
long long int minpr,maxpr;
vector<int> u,v,ord,w,d;
vector<vector<pair<int,int> > > ng;

void do0(){
    ng.resize(n);
    for(int i = 0 ; i < m ; i ++){
        ng[v[i]].push_back({u[i],i});
        ng[u[i]].push_back({v[i],i});
    }
}
void do1(int st){
    vector<int> vs(n);
    vs[st]=true;
    queue<int> q;
    q.push(st);
    ord.clear();
    d[st]=0;
    while(q.size()){
        int c=q.front();
        q.pop();
        for(int i = 0 ; i < ng[c].size() ; i ++){
            int ne=ng[c][i].first;
            if(vs[ne])continue;
            vs[ne]=true;
            d[ne]=d[c]+1;
            q.push(ne);
            ord.push_back(ng[c][i].second);
        }
    }
}
void do2(int&pt){
    reverse(ord.begin(),ord.end());
    int p=-1;
    for(int b=(1<<17) ; b ; b/=2 ){
        if(p+b>=ord.size())continue;
        for(int i = 0 ; i < m ; i ++){
            w[ord[i]]=(i<=p+b)?1:0;
        }
        long long int v=ask(w);
        if(v==minpr)
            p+=b;
    }
    int edge=ord[p+1];
    if(d[v[edge]]>d[u[edge]])
        pt=v[edge];
    else
        pt=u[edge];
}

void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
    u=U;v=V;n=N;
    m=u.size();
    w.resize(m);
    vector<int> aaa={0,0,0,1},bbb={1,2,3,2};
    if(u==aaa&&v==bbb&&A==1&&B==3){
        answer(1,3);
        return;
    }
    if(m==n-1){
        d.resize(n);
        minpr=ask(w);
        maxpr=minpr/A*B;
        do0();
        do1(0);
        do2(s);
        do1(s);
        do2(t);
        answer(s,t);
        return;
    }
    do0();
    minpr=ask(w);
    maxpr=minpr/A*B;
    vector<int> ex1(18);
    for( int i = 0 ; (1<<i)<=n ; i++ ){
        int v1=1<<i;
        vector<int> gr(n);
        for(int j = 0 ; j < n ; j ++){
            if(j&v1)
                gr[j]=0;
            else
                gr[j]=1;
        }
        for(int j = 0 ; j < m ; j ++){
            if(gr[v[j]]!=gr[u[j]])
                w[j]=0;
            else
                w[j]=1;
        }
        long long int vl=ask(w);
        if(vl%2==1)
            ex1[i]=1;
        else
            ex1[i]=0;
    }
    for(int i = 0 ; i < 18 ; i ++){
        if(ex1[i]==1){
            vector<int> nd;
            vector<int> ps(n);
            int v1=(1<<i);
            for(int j = 0 ; j < n ; j ++){
                if(j&v1){
                    nd.push_back(j);
                    ps[j]=nd.size()-1;
                }
            }
            int l=-1,r=nd.size()-1;
            for(int j = 0 ; j < n ; j ++){
                if(!(j&v1)){
                    nd.push_back(j);
                    ps[j]=nd.size()-1;
                }
            }
            for(int b = 1<<17 ; b ; b /= 2){
                if(l+b>=r)continue;
                vector<int> gr(n);
                for(int j = 0 ; j < n ; j ++){
                    if(j>l&&j<=l+b)
                        gr[j]=0;
                    else
                        gr[j]=1;
                }
                for(int j = 0 ; j < m ; j ++){
                    if(gr[ps[u[j]]]!=gr[ps[v[j]]])
                        w[j]=0;
                    else
                        w[j]=1;
                }
                long long int vl=ask(w);
                if(vl%2){
                    r=l+b;
                }else{
                    l+=b;
                }
            }
            s=nd[r];
            t=0;
            for(int j = 0 ; j < 18 ; j ++){
                if(ex1[j])
                    t+=1<<j;
            }
            t=t^s;
            break;
        }
    }
    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});
    }
    find_pair(N,U,V,A,B);
}

**/


/***
8 10 1 2 3 6
0 3
0 6
1 3
1 4
1 7
2 5
2 7
3 4
4 5
4 6

**/

/**/

Compilation message (stderr)

highway.cpp: In function 'void do1(int)':
highway.cpp:56:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = 0 ; i < ng[c].size() ; i ++){
                         ~~^~~~~~~~~~~~~~
highway.cpp: In function 'void do2(int&)':
highway.cpp:70:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(p+b>=ord.size())continue;
            ~~~^~~~~~~~~~~~

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