Submission #934900

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
934900	2024-02-28T06:53:14 Z	sleepntsheep	Highway Tolls (IOI18_highway)	C++17	6 / 100	121 ms	16512 KB

highway

#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]=a;else qq[i]=b;
        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;
        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]);
        vector<int> test(n);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
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	3 ms	4864 KB	Execution killed with signal 11
2	Halted	0 ms	0 KB	-

Subtask #2
0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	2612 KB	Output is correct
2	Correct	10 ms	3356 KB	Output is correct
3	Correct	77 ms	10120 KB	Output is correct
4	Correct	101 ms	9624 KB	Output is correct
5	Correct	78 ms	9664 KB	Output is correct
6	Correct	121 ms	9664 KB	Output is correct
7	Correct	112 ms	10116 KB	Output is correct
8	Correct	84 ms	9660 KB	Output is correct
9	Correct	79 ms	9692 KB	Output is correct
10	Correct	111 ms	9656 KB	Output is correct
11	Runtime error	81 ms	16512 KB	Execution killed with signal 11
12	Halted	0 ms	0 KB	-

Subtask #3
6.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	10 ms	3256 KB	Output is correct
2	Correct	27 ms	4012 KB	Output is correct
3	Correct	23 ms	4568 KB	Output is correct
4	Correct	72 ms	9008 KB	Output is correct
5	Correct	88 ms	9404 KB	Output is correct
6	Correct	117 ms	8976 KB	Output is correct
7	Correct	93 ms	9040 KB	Output is correct
8	Correct	72 ms	9040 KB	Output is correct
9	Correct	69 ms	9032 KB	Output is correct