oj.uz

Submission #934902

# Submission time Handle Problem Language Result Execution time Memory
934902 2024-02-28T06:57:02 Z sleepntsheep Highway Tolls (IOI18_highway) C++17
69 / 100
 177 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);for(int i=0;i<n;++i)if(~e[i])qq[e[i]]=1;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,0);
        for(int i=1;i<=y;++i)if(~e[c[i]])qq[e[c[i]]]=1;
        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 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:55:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   55 |         if(ask(qq)&1)return 1;return 0;
      |         ^~
highway.cpp:55:31: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   55 |         if(ask(qq)&1)return 1;return 0;
      |                               ^~~~~~
highway.cpp: In function 'void sub5()':
highway.cpp:70:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |         for(int i=0;i<gs.size()/2;++i)n1.push_back(gs[i]);
      |                     ~^~~~~~~~~~~~
highway.cpp:71:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |         for(int i=gs.size()/2;i<gs.size();++i)n2.push_back(gs[i]);
      |                               ~^~~~~~~~~~
highway.cpp:79:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |         for(int i=0;i<gt.size()/2;++i)n1.push_back(gt[i]);
      |                     ~^~~~~~~~~~~~
highway.cpp:80:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |         for(int i=gt.size()/2;i<gt.size();++i)n2.push_back(gt[i]);
      |                               ~^~~~~~~~~~
highway.cpp:50:9: warning: unused variable 'l' [-Wunused-variable]
   50 |     int l=0,r=n-1;
      |         ^
highway.cpp:50:13: warning: unused variable 'r' [-Wunused-variable]
   50 |     int l=0,r=n-1;
      |             ^
highway.cpp: In function 'void sub1234()':
highway.cpp:44:15: warning: 'e1' may be used uninitialized in this function [-Wmaybe-uninitialized]
   44 |     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 2 ms 2556 KB Output is correct
8 Correct 1 ms 2392 KB Output is correct
9 Correct 1 ms 2460 KB Output is correct
10 Correct 1 ms 2392 KB Output is correct
11 Correct 2 ms 2420 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 10 ms 3376 KB Output is correct
3 Correct 80 ms 9892 KB Output is correct
4 Correct 101 ms 10112 KB Output is correct
5 Correct 77 ms 9900 KB Output is correct
6 Correct 99 ms 9636 KB Output is correct
7 Correct 88 ms 9892 KB Output is correct
8 Correct 94 ms 9672 KB Output is correct
9 Correct 75 ms 9876 KB Output is correct
10 Correct 88 ms 10156 KB Output is correct
11 Correct 77 ms 9756 KB Output is correct
12 Correct 110 ms 9204 KB Output is correct
13 Correct 92 ms 9276 KB Output is correct
14 Correct 97 ms 9056 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 22 ms 3988 KB Output is correct
3 Correct 24 ms 4572 KB Output is correct
4 Correct 55 ms 9012 KB Output is correct
5 Correct 73 ms 9076 KB Output is correct
6 Correct 73 ms 9468 KB Output is correct
7 Correct 124 ms 9076 KB Output is correct
8 Correct 106 ms 9056 KB Output is correct
9 Correct 74 ms 9036 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 14 ms 3344 KB Output is correct
3 Correct 84 ms 8308 KB Output is correct
4 Correct 77 ms 9912 KB Output is correct
5 Correct 81 ms 9640 KB Output is correct
6 Correct 83 ms 9640 KB Output is correct
7 Correct 79 ms 9672 KB Output is correct
8 Correct 75 ms 9672 KB Output is correct
9 Correct 89 ms 9872 KB Output is correct
10 Correct 86 ms 10112 KB Output is correct
11 Correct 84 ms 9276 KB Output is correct
12 Correct 98 ms 9932 KB Output is correct
13 Correct 115 ms 8972 KB Output is correct
14 Correct 92 ms 9260 KB Output is correct
15 Correct 84 ms 9928 KB Output is correct
16 Correct 72 ms 9680 KB Output is correct
17 Correct 108 ms 9084 KB Output is correct
18 Correct 86 ms 9280 KB Output is correct
19 Correct 73 ms 9700 KB Output is correct
20 Correct 86 ms 9016 KB Output is correct
21 Correct 66 ms 10340 KB Output is correct
22 Correct 73 ms 10004 KB Output is correct
23 Correct 118 ms 10116 KB Output is correct
24 Correct 119 ms 9988 KB Output is correct
25 Correct 89 ms 10028 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 3432 KB Output is correct
2 Correct 18 ms 3468 KB Output is correct
3 Correct 148 ms 10544 KB Output is correct
4 Correct 97 ms 11320 KB Output is correct
5 Correct 105 ms 12168 KB Output is correct
6 Correct 133 ms 12044 KB Output is correct
7 Correct 123 ms 12248 KB Output is correct
8 Correct 134 ms 12392 KB Output is correct
9 Correct 121 ms 9448 KB Output is correct
10 Correct 119 ms 10148 KB Output is correct
11 Correct 96 ms 10296 KB Output is correct
12 Correct 135 ms 11996 KB Output is correct
13 Correct 119 ms 12308 KB Output is correct
14 Correct 104 ms 12128 KB Output is correct
15 Correct 142 ms 12188 KB Output is correct
16 Correct 103 ms 10816 KB Output is correct
17 Correct 82 ms 10388 KB Output is correct
18 Correct 81 ms 10824 KB Output is correct
19 Correct 80 ms 10280 KB Output is correct
20 Correct 97 ms 10668 KB Output is correct
21 Correct 177 ms 12284 KB Output is correct

Subtask #6
0 / 31.0

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