oj.uz

Submission #124415

# Submission time Handle Problem Language Result Execution time Memory
124415 2019-07-03T10:03:01 Z forelax Highway Tolls (IOI18_highway) C++14
69 / 100
 316 ms 11624 KB 
#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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 408 KB Output is correct
2 Correct 2 ms 316 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 2 ms 412 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 248 KB Output is correct
7 Correct 2 ms 248 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 316 KB Output is correct
10 Correct 2 ms 296 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 380 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 26 ms 1416 KB Output is correct
3 Correct 217 ms 9632 KB Output is correct
4 Correct 175 ms 9636 KB Output is correct
5 Correct 208 ms 9580 KB Output is correct
6 Correct 206 ms 9640 KB Output is correct
7 Correct 227 ms 9648 KB Output is correct
8 Correct 190 ms 9608 KB Output is correct
9 Correct 240 ms 9644 KB Output is correct
10 Correct 226 ms 9660 KB Output is correct
11 Correct 211 ms 9036 KB Output is correct
12 Correct 222 ms 9036 KB Output is correct
13 Correct 219 ms 9084 KB Output is correct
14 Correct 216 ms 9012 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 1272 KB Output is correct
2 Correct 35 ms 2276 KB Output is correct
3 Correct 61 ms 3204 KB Output is correct
4 Correct 168 ms 9084 KB Output is correct
5 Correct 163 ms 9080 KB Output is correct
6 Correct 168 ms 9036 KB Output is correct
7 Correct 129 ms 9000 KB Output is correct
8 Correct 164 ms 9080 KB Output is correct
9 Correct 177 ms 9012 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 348 KB Output is correct
2 Correct 20 ms 1396 KB Output is correct
3 Correct 176 ms 7684 KB Output is correct
4 Correct 212 ms 9576 KB Output is correct
5 Correct 208 ms 9616 KB Output is correct
6 Correct 207 ms 9636 KB Output is correct
7 Correct 201 ms 9648 KB Output is correct
8 Correct 213 ms 9636 KB Output is correct
9 Correct 251 ms 9632 KB Output is correct
10 Correct 221 ms 9640 KB Output is correct
11 Correct 225 ms 9092 KB Output is correct
12 Correct 214 ms 8988 KB Output is correct
13 Correct 219 ms 9140 KB Output is correct
14 Correct 225 ms 9036 KB Output is correct
15 Correct 210 ms 9592 KB Output is correct
16 Correct 226 ms 9640 KB Output is correct
17 Correct 228 ms 9040 KB Output is correct
18 Correct 218 ms 9084 KB Output is correct
19 Correct 218 ms 9644 KB Output is correct
20 Correct 215 ms 8996 KB Output is correct
21 Correct 197 ms 10156 KB Output is correct
22 Correct 171 ms 10040 KB Output is correct
23 Correct 180 ms 9968 KB Output is correct
24 Correct 172 ms 9840 KB Output is correct
25 Correct 195 ms 9052 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 1408 KB Output is correct
2 Correct 25 ms 1448 KB Output is correct
3 Correct 239 ms 9948 KB Output is correct
4 Correct 253 ms 10560 KB Output is correct
5 Correct 303 ms 11568 KB Output is correct
6 Correct 311 ms 11568 KB Output is correct
7 Correct 270 ms 11588 KB Output is correct
8 Correct 306 ms 11564 KB Output is correct
9 Correct 265 ms 7904 KB Output is correct
10 Correct 256 ms 8320 KB Output is correct
11 Correct 272 ms 8912 KB Output is correct
12 Correct 293 ms 10568 KB Output is correct
13 Correct 286 ms 10956 KB Output is correct
14 Correct 296 ms 11572 KB Output is correct
15 Correct 307 ms 11580 KB Output is correct
16 Correct 279 ms 9088 KB Output is correct
17 Correct 216 ms 9752 KB Output is correct
18 Correct 194 ms 10024 KB Output is correct
19 Correct 199 ms 9828 KB Output is correct
20 Correct 210 ms 9888 KB Output is correct
21 Correct 316 ms 11624 KB Output is correct

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 21 ms 1420 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -