oj.uz

Submission #124438

# Submission time Handle Problem Language Result Execution time Memory
124438 2019-07-03T10:39:55 Z forelax Highway Tolls (IOI18_highway) C++14
51 / 100
 439 ms 29396 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,tmp;
vector<int> u,v,ord,w,d;
vector<vector<pair<long long 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){
    w.clear();
    w.resize(m,1);
    for(int i = 0 ; i < s0.size() ; i ++){
        w[s0[i][1]]=0;
    }
    long long int q=ask(w);
    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 < md ; i ++)
            w[s0[i][1]]=0;
        tmp=ask(w);
        if(tmp==q){
            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.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.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;
        }
    }
    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());
    t=fnd(s1);
    s=fnd(s2);
    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);
}
*/

Compilation message

highway.cpp: In function 'std::vector<std::vector<int> > bfs(int, int)':
highway.cpp:51: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> >)':
highway.cpp:66:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0 ; i < s0.size() ; i ++){
                     ~~^~~~~~~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 632 KB Output is correct
2 Correct 45 ms 3504 KB Output is correct
3 Correct 418 ms 29396 KB Output is correct
4 Correct 433 ms 29208 KB Output is correct
5 Correct 412 ms 29260 KB Output is correct
6 Correct 415 ms 29292 KB Output is correct
7 Correct 439 ms 29292 KB Output is correct
8 Correct 421 ms 29360 KB Output is correct
9 Correct 410 ms 29292 KB Output is correct
10 Correct 431 ms 29276 KB Output is correct
11 Correct 356 ms 27060 KB Output is correct
12 Correct 353 ms 28056 KB Output is correct
13 Correct 329 ms 28928 KB Output is correct
14 Correct 364 ms 28720 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 3412 KB Output is correct
2 Correct 79 ms 6496 KB Output is correct
3 Correct 81 ms 9672 KB Output is correct
4 Correct 240 ms 27004 KB Output is correct
5 Correct 240 ms 27044 KB Output is correct
6 Correct 230 ms 28012 KB Output is correct
7 Correct 229 ms 28648 KB Output is correct
8 Correct 240 ms 27444 KB Output is correct
9 Correct 192 ms 27636 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 632 KB Output is correct
2 Correct 57 ms 3276 KB Output is correct
3 Correct 308 ms 22884 KB Output is correct
4 Correct 398 ms 29368 KB Output is correct
5 Correct 391 ms 29288 KB Output is correct
6 Correct 409 ms 29288 KB Output is correct
7 Correct 426 ms 29312 KB Output is correct
8 Correct 411 ms 29368 KB Output is correct
9 Correct 411 ms 29080 KB Output is correct
10 Correct 410 ms 29292 KB Output is correct
11 Correct 393 ms 29152 KB Output is correct
12 Correct 378 ms 28500 KB Output is correct
13 Correct 366 ms 28100 KB Output is correct
14 Correct 357 ms 27400 KB Output is correct
15 Correct 415 ms 29328 KB Output is correct
16 Correct 412 ms 29296 KB Output is correct
17 Correct 381 ms 28676 KB Output is correct
18 Correct 339 ms 28896 KB Output is correct
19 Correct 414 ms 29292 KB Output is correct
20 Correct 349 ms 28724 KB Output is correct
21 Correct 348 ms 28880 KB Output is correct
22 Correct 406 ms 28896 KB Output is correct
23 Correct 382 ms 26452 KB Output is correct
24 Correct 387 ms 26604 KB Output is correct
25 Correct 360 ms 28688 KB Output is correct

Subtask #5
0 / 18.0

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

Subtask #6
0 / 31.0

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