oj.uz

Submission #934908

# Submission time Handle Problem Language Result Execution time Memory
934908 2024-02-28T07:26:46 Z sleepntsheep Highway Tolls (IOI18_highway) C++17
69 / 100
 127 ms 12444 KB 
#include "highway.h"
#include<bits/stdc++.h>
using namespace std;

int n,m,a,b;std::vector<int>u,v;std::vector<std::pair<int,int>>g[90001];

int sub12(int src,int ban)
{
    vector<int>d(n,1e9),e(n,-1);
    queue<pair<int,int>>q; q.emplace(d[src]=0,src);
    while(q.size()){auto[c,u]=q.front();q.pop();for(auto[v,i]:g[u])if(ban-i&&d[v]>c+1)q.emplace(d[v]=c+1,v),e[v]=i;}

    long long need; {vector<int>qq(m,1);for(int i=0;i<n;++i)if(~e[i])qq[e[i]]=0;need=ask(qq);}

    vector<int>c;
    for(int i=0;i<n;++i)if(d[i]<1e9)c.push_back(i);
    sort(c.begin(),c.end(),[&d](int i,int v){return d[i]<d[v];});

    int z=0,l=0,r=c.size()-1;
    while(l<=r){
        int y=(l+r)/2;
        vector<int>qq(m,1);
        for(int i=1;i<=y;++i)if(~e[c[i]])qq[e[c[i]]]=0;
        if (ask(qq)==need)z=c[y],r=y-1;
        else l=y+1;
    }

    return z;
}

void sub1234(){
    long long need; {vector<int>qq(m,1); need=ask(qq);}
    auto dt = need / b;
    long long light = dt * a;

    int e1,l=0,r=m-1;
    while(l<=r) {
        int y=(l+r)/2;
        vector<int>qq(m);
        for(int i=0;i<=y;++i)qq[i]=1;
        if(ask(qq)>light)r=y-1,e1=y;
        else l=y+1;
    }

    int p=u[e1],q=v[e1],s=sub12(p,e1),t=sub12(q,e1);

    answer(s,t);
}

void sub6()
{
    long long need; {vector<int>qq(m,0); need=ask(qq);}

    int e1,l=0,r=m-1;
    while(l<=r) {
        int y=(l+r)/2;
        vector<int>qq(m);
        for(int i=0;i<=y;++i)qq[i]=1;
        if(ask(qq)>need)r=y-1,e1=y;
        else l=y+1;
    }

    int p=u[e1],q=v[e1],s=sub12(p,e1),t=sub12(q,e1);

    answer(s,t);
}

void sub5(){
    int l=0,r=n-1;

    auto diffset = [&](vector<int>&grp){
        vector<int>qq(m);
        for(int i=0;i<m;++i)if(grp[u[i]]^grp[v[i]])qq[i]=0;else qq[i]=1;
        if(ask(qq)&1)return 1;return 0;
    };

    vector<int> gs,gt,grp(n);

    for(int b=0;b<=17;++b){
        for(int i=0;i<n;++i)
            grp[i]=(i>>b)&1;
        if(diffset(grp)) {break;}
    }

    for(int i=0;i<n;++i)if(grp[i])gt.push_back(i);else gs.push_back(i);

    while(gs.size()>1){
        vector<int>n1,n2,test(n);
        for(int i=0;i<gs.size()/2;++i)n1.push_back(gs[i]);
        for(int i=gs.size()/2;i<gs.size();++i)n2.push_back(gs[i]);
        for(int x:n1)test[x]=1;
        if(diffset(test))gs=n1;
        else gs=n2;
    }

    while(gt.size()>1){
        vector<int>n1,n2;
        for(int i=0;i<gt.size()/2;++i)n1.push_back(gt[i]);
        for(int i=gt.size()/2;i<gt.size();++i)n2.push_back(gt[i]);
        vector<int> test(n);for(int x:n1)test[x]=1;
        if(diffset(test))gt=n1;
        else gt=n2;
    }

    answer(gs[0],gt[0]);
}


void find_pair(int n_, std::vector<int> u_, std::vector<int> v_, int A_, int B_) {
    n=n_,u=u_,v=v_,a=A_,b=B_;m=u.size();
    for(int i=0;i<m;++i)g[u[i]].push_back({v[i],i}),g[v[i]].push_back({u[i],i});

    if(a==1&&b==2)return sub5();
    sub1234();

}

Compilation message

highway.cpp: In lambda function:
highway.cpp:74:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   74 |         if(ask(qq)&1)return 1;return 0;
      |         ^~
highway.cpp:74:31: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   74 |         if(ask(qq)&1)return 1;return 0;
      |                               ^~~~~~
highway.cpp: In function 'void sub5()':
highway.cpp:89:22: 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<gs.size()/2;++i)n1.push_back(gs[i]);
      |                     ~^~~~~~~~~~~~
highway.cpp:90:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |         for(int i=gs.size()/2;i<gs.size();++i)n2.push_back(gs[i]);
      |                               ~^~~~~~~~~~
highway.cpp:98:22: 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<gt.size()/2;++i)n1.push_back(gt[i]);
      |                     ~^~~~~~~~~~~~
highway.cpp:99:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |         for(int i=gt.size()/2;i<gt.size();++i)n2.push_back(gt[i]);
      |                               ~^~~~~~~~~~
highway.cpp:69:9: warning: unused variable 'l' [-Wunused-variable]
   69 |     int l=0,r=n-1;
      |         ^
highway.cpp:69:13: warning: unused variable 'r' [-Wunused-variable]
   69 |     int l=0,r=n-1;
      |             ^
highway.cpp: In function 'void sub1234()':
highway.cpp:45:15: warning: 'e1' may be used uninitialized in this function [-Wmaybe-uninitialized]
   45 |     int p=u[e1],q=v[e1],s=sub12(p,e1),t=sub12(q,e1);
      |               ^
highway.cpp: In function 'void sub6()':
highway.cpp:63:46: warning: 'e1' may be used uninitialized in this function [-Wmaybe-uninitialized]
   63 |     int p=u[e1],q=v[e1],s=sub12(p,e1),t=sub12(q,e1);
      |                                         ~~~~~^~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 2 ms 2392 KB Output is correct
4 Correct 1 ms 2392 KB Output is correct
5 Correct 1 ms 2556 KB Output is correct
6 Correct 1 ms 2392 KB Output is correct
7 Correct 1 ms 2560 KB Output is correct
8 Correct 1 ms 2392 KB Output is correct
9 Correct 1 ms 2320 KB Output is correct
10 Correct 2 ms 2392 KB Output is correct
11 Correct 1 ms 2392 KB Output is correct
12 Correct 2 ms 2540 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2612 KB Output is correct
2 Correct 10 ms 3352 KB Output is correct
3 Correct 89 ms 9888 KB Output is correct
4 Correct 93 ms 10108 KB Output is correct
5 Correct 90 ms 9920 KB Output is correct
6 Correct 83 ms 9632 KB Output is correct
7 Correct 86 ms 9888 KB Output is correct
8 Correct 74 ms 9672 KB Output is correct
9 Correct 91 ms 10160 KB Output is correct
10 Correct 85 ms 10128 KB Output is correct
11 Correct 78 ms 9560 KB Output is correct
12 Correct 80 ms 9256 KB Output is correct
13 Correct 93 ms 9044 KB Output is correct
14 Correct 94 ms 9248 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 3256 KB Output is correct
2 Correct 17 ms 4260 KB Output is correct
3 Correct 24 ms 5176 KB Output is correct
4 Correct 60 ms 9284 KB Output is correct
5 Correct 68 ms 9012 KB Output is correct
6 Correct 69 ms 9208 KB Output is correct
7 Correct 74 ms 9148 KB Output is correct
8 Correct 68 ms 9280 KB Output is correct
9 Correct 68 ms 9012 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2616 KB Output is correct
2 Correct 10 ms 3364 KB Output is correct
3 Correct 67 ms 8300 KB Output is correct
4 Correct 86 ms 9868 KB Output is correct
5 Correct 75 ms 9644 KB Output is correct
6 Correct 80 ms 9632 KB Output is correct
7 Correct 86 ms 9888 KB Output is correct
8 Correct 74 ms 9676 KB Output is correct
9 Correct 91 ms 9636 KB Output is correct
10 Correct 91 ms 9668 KB Output is correct
11 Correct 94 ms 9040 KB Output is correct
12 Correct 101 ms 9684 KB Output is correct
13 Correct 91 ms 8972 KB Output is correct
14 Correct 98 ms 9092 KB Output is correct
15 Correct 79 ms 10012 KB Output is correct
16 Correct 78 ms 10008 KB Output is correct
17 Correct 98 ms 9252 KB Output is correct
18 Correct 91 ms 9256 KB Output is correct
19 Correct 75 ms 9660 KB Output is correct
20 Correct 87 ms 9072 KB Output is correct
21 Correct 71 ms 10360 KB Output is correct
22 Correct 69 ms 10056 KB Output is correct
23 Correct 93 ms 10112 KB Output is correct
24 Correct 84 ms 10016 KB Output is correct
25 Correct 76 ms 9648 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 3436 KB Output is correct
2 Correct 12 ms 3500 KB Output is correct
3 Correct 93 ms 10968 KB Output is correct
4 Correct 98 ms 10992 KB Output is correct
5 Correct 110 ms 12396 KB Output is correct
6 Correct 126 ms 12180 KB Output is correct
7 Correct 108 ms 12352 KB Output is correct
8 Correct 127 ms 12356 KB Output is correct
9 Correct 96 ms 9448 KB Output is correct
10 Correct 104 ms 10240 KB Output is correct
11 Correct 105 ms 10556 KB Output is correct
12 Correct 112 ms 12116 KB Output is correct
13 Correct 122 ms 12180 KB Output is correct
14 Correct 109 ms 12444 KB Output is correct
15 Correct 108 ms 12176 KB Output is correct
16 Correct 100 ms 11040 KB Output is correct
17 Correct 81 ms 10208 KB Output is correct
18 Correct 72 ms 10672 KB Output is correct
19 Correct 79 ms 10752 KB Output is correct
20 Correct 87 ms 10616 KB Output is correct
21 Correct 105 ms 12124 KB Output is correct

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 3396 KB Output is correct
2 Correct 13 ms 3444 KB Output is correct
3 Partially correct 115 ms 10688 KB Output is partially correct
4 Partially correct 113 ms 10540 KB Output is partially correct
5 Incorrect 120 ms 11056 KB Output isn't correct
6 Halted 0 ms 0 KB -