oj.uz

Submission #934907

# Submission time Handle Problem Language Result Execution time Memory
934907 2024-02-28T07:25:29 Z sleepntsheep Highway Tolls (IOI18_highway) C++17
18 / 100
 117 ms 12688 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,0);
        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:73:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   73 |         if(ask(qq)&1)return 1;return 0;
      |         ^~
highway.cpp:73:31: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   73 |         if(ask(qq)&1)return 1;return 0;
      |                               ^~~~~~
highway.cpp: In function 'void sub5()':
highway.cpp:88:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |         for(int i=0;i<gs.size()/2;++i)n1.push_back(gs[i]);
      |                     ~^~~~~~~~~~~~
highway.cpp:89:32: 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=gs.size()/2;i<gs.size();++i)n2.push_back(gs[i]);
      |                               ~^~~~~~~~~~
highway.cpp:97:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |         for(int i=0;i<gt.size()/2;++i)n1.push_back(gt[i]);
      |                     ~^~~~~~~~~~~~
highway.cpp:98:32: 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=gt.size()/2;i<gt.size();++i)n2.push_back(gt[i]);
      |                               ~^~~~~~~~~~
highway.cpp:68:9: warning: unused variable 'l' [-Wunused-variable]
   68 |     int l=0,r=n-1;
      |         ^
highway.cpp:68:13: warning: unused variable 'r' [-Wunused-variable]
   68 |     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);
      |               ^
highway.cpp: In function 'void sub6()':
highway.cpp:62:46: warning: 'e1' may be used uninitialized in this function [-Wmaybe-uninitialized]
   62 |     int p=u[e1],q=v[e1],s=sub12(p,e1),t=sub12(q,e1);
      |                                         ~~~~~^~~~~~

Subtask #1
0 / 5.0

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

Subtask #2
0 / 7.0

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

Subtask #3
0 / 6.0

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

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2620 KB Output is correct
2 Incorrect 10 ms 3364 KB Output is incorrect: {s, t} is wrong.
3 Halted 0 ms 0 KB -

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 3456 KB Output is correct
2 Correct 13 ms 3588 KB Output is correct
3 Correct 94 ms 10664 KB Output is correct
4 Correct 104 ms 11316 KB Output is correct
5 Correct 116 ms 11952 KB Output is correct
6 Correct 116 ms 12028 KB Output is correct
7 Correct 115 ms 12008 KB Output is correct
8 Correct 104 ms 12248 KB Output is correct
9 Correct 105 ms 10120 KB Output is correct
10 Correct 91 ms 10136 KB Output is correct
11 Correct 89 ms 10756 KB Output is correct
12 Correct 110 ms 11676 KB Output is correct
13 Correct 117 ms 12112 KB Output is correct
14 Correct 107 ms 12396 KB Output is correct
15 Correct 114 ms 12500 KB Output is correct
16 Correct 99 ms 10760 KB Output is correct
17 Correct 84 ms 10404 KB Output is correct
18 Correct 78 ms 10664 KB Output is correct
19 Correct 84 ms 10572 KB Output is correct
20 Correct 81 ms 10928 KB Output is correct
21 Correct 116 ms 12688 KB Output is correct

Subtask #6
0 / 31.0

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