oj.uz

Submission #934928

# Submission time Handle Problem Language Result Execution time Memory
934928 2024-02-28T08:00:34 Z sleepntsheep Highway Tolls (IOI18_highway) C++17
51 / 100
 145 ms 12028 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;qq[ban]=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);
        qq[ban]=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);
}

auto shortpath(int src){
    vector<int>d(n,1e9);
    queue<pair<int,int>>q;q.emplace(d[src]=0,src);
    while(q.size()){auto[c,u]=q.front();q.pop();for(auto [v,_]:g[u])if(d[v]>c+1)q.emplace(d[v]=c+1,v);}
    return d;
}

int tree(int rt,int*S,int*T,int e1){
    vector<int>d(n,1e9),e(n,-1);
    queue<pair<int,int>>q; q.emplace(d[rt]=0,rt);
    while(q.size()){auto[c,u]=q.front();q.pop();for(auto[v,i]:g[u])if(S[v]&&d[v]>c+1)q.emplace(d[v]=c+1,v),e[v]=i;}

    long long need;
    {
        vector<int>qq(m,0);
        for(int i=0;i<m;++i)
        {
            if((S[u[i]]&&S[v[i]]))qq[i]=0;
            else if((T[u[i]]&&T[v[i]]))qq[i]=1;
            else qq[i]=1;
        }
        qq[e1]=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];});

    //printf(" C is : ");for(int x : c)printf("%d ",x);puts("");

    int z=rt,l=0,r=c.size()-1;
    while(l<=r){
        int y=(l+r)/2;
        vector<int>qq(m,1);
        for(int i=0;i<m;++i){
            if((S[u[i]]&&S[v[i]]))qq[i]=1;
            else if((T[u[i]]&&T[v[i]]))qq[i]=1;
            else qq[i]=1;
        }

        for(int i=0;i<=y;++i)if(~e[c[i]])qq[e[c[i]]]=0;
        qq[e1]=0;
        if (ask(qq)==need)z=c[y],r=y-1;
        else l=y+1;
    }

    return z;
}

int S[90000],T[90000];
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 U=u[e1],V=v[e1];

    auto du=shortpath(U),dv=shortpath(V);

    for(int i=0;i<n;++i){if(du[i]<dv[i])S[i]=1;if(dv[i]<du[i])T[i]=1;}

    int s = tree(U,S,T,e1);
    int t = tree(V,T,S,e1);
    //printf(" ST %d %d\n",s,t);
    answer(s,t);
}

void sub5();

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();

}

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]); }

Compilation message

highway.cpp: In function 'void sub5()':
highway.cpp:139:427: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  139 | 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]); }
      |                                                                                                                                                                                                                                                                                                                                                                                                                                          ~^~~~~~~~~~~~
highway.cpp:139:488: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  139 | 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]); }
      |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                       ~^~~~~~~~~~
highway.cpp:139:637: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  139 | 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]); }
      |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                            ~^~~~~~~~~~~~
highway.cpp:139:698: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  139 | 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]); }
      |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                         ~^~~~~~~~~~
highway.cpp:139:18: warning: unused variable 'l' [-Wunused-variable]
  139 | 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]); }
      |                  ^
highway.cpp:139:22: warning: unused variable 'r' [-Wunused-variable]
  139 | 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]); }
      |                      ^
highway.cpp: In function 'void sub6()':
highway.cpp:115:15: warning: 'e1' may be used uninitialized in this function [-Wmaybe-uninitialized]
  115 |     int U=u[e1],V=v[e1];
      |               ^
highway.cpp: In function 'void sub1234()':
highway.cpp:46:15: warning: 'e1' may be used uninitialized in this function [-Wmaybe-uninitialized]
   46 |     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 2904 KB Output is correct
2 Correct 1 ms 2904 KB Output is correct
3 Correct 1 ms 2904 KB Output is correct
4 Correct 1 ms 2904 KB Output is correct
5 Correct 1 ms 3096 KB Output is correct
6 Correct 1 ms 2904 KB Output is correct
7 Correct 1 ms 3100 KB Output is correct
8 Correct 1 ms 2904 KB Output is correct
9 Correct 1 ms 2904 KB Output is correct
10 Correct 1 ms 2904 KB Output is correct
11 Correct 1 ms 3156 KB Output is correct
12 Correct 1 ms 2904 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3156 KB Output is correct
2 Correct 10 ms 4256 KB Output is correct
3 Correct 110 ms 11440 KB Output is correct
4 Correct 108 ms 11644 KB Output is correct
5 Correct 135 ms 11564 KB Output is correct
6 Correct 145 ms 11508 KB Output is correct
7 Correct 115 ms 11776 KB Output is correct
8 Correct 126 ms 11240 KB Output is correct
9 Correct 123 ms 11168 KB Output is correct
10 Correct 120 ms 11300 KB Output is correct
11 Correct 127 ms 10576 KB Output is correct
12 Correct 114 ms 10844 KB Output is correct
13 Correct 101 ms 10672 KB Output is correct
14 Correct 116 ms 10672 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 3904 KB Output is correct
2 Correct 26 ms 4784 KB Output is correct
3 Correct 24 ms 5696 KB Output is correct
4 Correct 102 ms 10420 KB Output is correct
5 Correct 104 ms 10536 KB Output is correct
6 Correct 113 ms 10316 KB Output is correct
7 Correct 69 ms 10276 KB Output is correct
8 Correct 77 ms 10372 KB Output is correct
9 Correct 78 ms 10444 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3160 KB Output is correct
2 Correct 12 ms 4008 KB Output is correct
3 Correct 78 ms 9248 KB Output is correct
4 Correct 93 ms 11292 KB Output is correct
5 Correct 103 ms 10940 KB Output is correct
6 Correct 88 ms 11044 KB Output is correct
7 Correct 109 ms 10952 KB Output is correct
8 Correct 99 ms 11124 KB Output is correct
9 Correct 113 ms 11720 KB Output is correct
10 Correct 102 ms 11644 KB Output is correct
11 Correct 136 ms 10912 KB Output is correct
12 Correct 121 ms 10800 KB Output is correct
13 Correct 118 ms 10896 KB Output is correct
14 Correct 130 ms 11112 KB Output is correct
15 Correct 94 ms 11220 KB Output is correct
16 Correct 88 ms 11080 KB Output is correct
17 Correct 136 ms 10896 KB Output is correct
18 Correct 134 ms 10676 KB Output is correct
19 Correct 87 ms 10908 KB Output is correct
20 Correct 119 ms 10424 KB Output is correct
21 Correct 95 ms 11984 KB Output is correct
22 Correct 114 ms 11560 KB Output is correct
23 Correct 108 ms 12028 KB Output is correct
24 Correct 99 ms 11192 KB Output is correct
25 Correct 141 ms 10568 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 18 ms 4256 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 Incorrect 14 ms 4208 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -