oj.uz

Submission #934913

# Submission time Handle Problem Language Result Execution time Memory
934913 2024-02-28T07:29:42 Z sleepntsheep Highway Tolls (IOI18_highway) C++17
69 / 100
 157 ms 12392 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 light; {vector<int>qq(m,0); light=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)>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 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});

    //sub6();
    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 1 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 2552 KB Output is correct
8 Correct 1 ms 2392 KB Output is correct
9 Correct 1 ms 2392 KB Output is correct
10 Correct 2 ms 2392 KB Output is correct
11 Correct 1 ms 2392 KB Output is correct
12 Correct 1 ms 2392 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2616 KB Output is correct
2 Correct 13 ms 3376 KB Output is correct
3 Correct 83 ms 9896 KB Output is correct
4 Correct 128 ms 9900 KB Output is correct
5 Correct 117 ms 9676 KB Output is correct
6 Correct 88 ms 9632 KB Output is correct
7 Correct 129 ms 10156 KB Output is correct
8 Correct 92 ms 9664 KB Output is correct
9 Correct 109 ms 9688 KB Output is correct
10 Correct 102 ms 9888 KB Output is correct
11 Correct 82 ms 9520 KB Output is correct
12 Correct 114 ms 8984 KB Output is correct
13 Correct 103 ms 9260 KB Output is correct
14 Correct 99 ms 9016 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 3236 KB Output is correct
2 Correct 16 ms 4464 KB Output is correct
3 Correct 23 ms 4672 KB Output is correct
4 Correct 79 ms 9024 KB Output is correct
5 Correct 83 ms 9156 KB Output is correct
6 Correct 82 ms 9068 KB Output is correct
7 Correct 90 ms 9028 KB Output is correct
8 Correct 75 ms 9076 KB Output is correct
9 Correct 73 ms 8968 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2624 KB Output is correct
2 Correct 12 ms 3412 KB Output is correct
3 Correct 68 ms 7988 KB Output is correct
4 Correct 82 ms 9876 KB Output is correct
5 Correct 78 ms 9924 KB Output is correct
6 Correct 93 ms 9872 KB Output is correct
7 Correct 81 ms 10136 KB Output is correct
8 Correct 85 ms 10128 KB Output is correct
9 Correct 107 ms 9856 KB Output is correct
10 Correct 92 ms 9880 KB Output is correct
11 Correct 116 ms 9280 KB Output is correct
12 Correct 96 ms 9224 KB Output is correct
13 Correct 117 ms 9204 KB Output is correct
14 Correct 102 ms 9260 KB Output is correct
15 Correct 63 ms 9988 KB Output is correct
16 Correct 91 ms 9688 KB Output is correct
17 Correct 99 ms 9264 KB Output is correct
18 Correct 91 ms 9272 KB Output is correct
19 Correct 75 ms 9660 KB Output is correct
20 Correct 87 ms 9092 KB Output is correct
21 Correct 89 ms 10472 KB Output is correct
22 Correct 96 ms 9992 KB Output is correct
23 Correct 98 ms 9856 KB Output is correct
24 Correct 87 ms 10120 KB Output is correct
25 Correct 104 ms 9780 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 3460 KB Output is correct
2 Correct 17 ms 3480 KB Output is correct
3 Correct 108 ms 10708 KB Output is correct
4 Correct 109 ms 11140 KB Output is correct
5 Correct 121 ms 12092 KB Output is correct
6 Correct 125 ms 12284 KB Output is correct
7 Correct 109 ms 12168 KB Output is correct
8 Correct 137 ms 12392 KB Output is correct
9 Correct 144 ms 9672 KB Output is correct
10 Correct 96 ms 9920 KB Output is correct
11 Correct 109 ms 10420 KB Output is correct
12 Correct 143 ms 11808 KB Output is correct
13 Correct 106 ms 12196 KB Output is correct
14 Correct 134 ms 12096 KB Output is correct
15 Correct 115 ms 12324 KB Output is correct
16 Correct 145 ms 10812 KB Output is correct
17 Correct 74 ms 10400 KB Output is correct
18 Correct 78 ms 10496 KB Output is correct
19 Correct 106 ms 10540 KB Output is correct
20 Correct 88 ms 10656 KB Output is correct
21 Correct 118 ms 12260 KB Output is correct

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 3500 KB Output is correct
2 Correct 17 ms 3432 KB Output is correct
3 Partially correct 157 ms 10592 KB Output is partially correct
4 Partially correct 125 ms 10780 KB Output is partially correct
5 Incorrect 157 ms 11196 KB Output isn't correct
6 Halted 0 ms 0 KB -