oj.uz

Submission #934915

# Submission time Handle Problem Language Result Execution time Memory
934915 2024-02-28T07:30:23 Z sleepntsheep Highway Tolls (IOI18_highway) C++17
51 / 100
 131 ms 11052 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});

    return 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 2 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 2804 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 2388 KB Output is correct
11 Correct 2 ms 2392 KB Output is correct
12 Correct 2 ms 2392 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2620 KB Output is correct
2 Correct 13 ms 3372 KB Output is correct
3 Correct 88 ms 9888 KB Output is correct
4 Correct 104 ms 9700 KB Output is correct
5 Correct 107 ms 9900 KB Output is correct
6 Correct 83 ms 9640 KB Output is correct
7 Correct 91 ms 10152 KB Output is correct
8 Correct 92 ms 9696 KB Output is correct
9 Correct 99 ms 9664 KB Output is correct
10 Correct 106 ms 9672 KB Output is correct
11 Correct 92 ms 9024 KB Output is correct
12 Correct 108 ms 8972 KB Output is correct
13 Correct 106 ms 9068 KB Output is correct
14 Correct 107 ms 9240 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 3260 KB Output is correct
2 Correct 23 ms 3984 KB Output is correct
3 Correct 29 ms 4796 KB Output is correct
4 Correct 65 ms 9244 KB Output is correct
5 Correct 80 ms 9008 KB Output is correct
6 Correct 69 ms 8984 KB Output is correct
7 Correct 71 ms 9280 KB Output is correct
8 Correct 92 ms 9040 KB Output is correct
9 Correct 80 ms 9024 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2868 KB Output is correct
2 Correct 14 ms 3348 KB Output is correct
3 Correct 65 ms 7988 KB Output is correct
4 Correct 84 ms 9660 KB Output is correct
5 Correct 111 ms 9652 KB Output is correct
6 Correct 78 ms 9640 KB Output is correct
7 Correct 81 ms 9660 KB Output is correct
8 Correct 95 ms 9884 KB Output is correct
9 Correct 129 ms 9868 KB Output is correct
10 Correct 130 ms 9672 KB Output is correct
11 Correct 103 ms 9504 KB Output is correct
12 Correct 98 ms 9676 KB Output is correct
13 Correct 98 ms 9656 KB Output is correct
14 Correct 128 ms 9044 KB Output is correct
15 Correct 83 ms 9660 KB Output is correct
16 Correct 74 ms 9836 KB Output is correct
17 Correct 101 ms 9040 KB Output is correct
18 Correct 96 ms 9280 KB Output is correct
19 Correct 85 ms 9656 KB Output is correct
20 Correct 90 ms 9108 KB Output is correct
21 Correct 117 ms 10340 KB Output is correct
22 Correct 121 ms 10232 KB Output is correct
23 Correct 131 ms 10080 KB Output is correct
24 Correct 85 ms 9996 KB Output is correct
25 Correct 114 ms 9136 KB Output is correct

Subtask #5
0 / 18.0

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

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 3400 KB Output is correct
2 Correct 12 ms 3452 KB Output is correct
3 Partially correct 117 ms 10956 KB Output is partially correct
4 Partially correct 119 ms 10756 KB Output is partially correct
5 Incorrect 120 ms 11052 KB Output isn't correct
6 Halted 0 ms 0 KB -