oj.uz

답안 #934925

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
934925 2024-02-28T07:57:47 Z sleepntsheep 통행료 (IOI18_highway) C++17
7 / 100
 1346 ms 15024 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,std::set<int>&S,std::set<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.count(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.count(u[i])&&S.count(v[i])))qq[i]=0;
            else if((T.count(u[i])&&T.count(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(~e[i])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.count(u[i])&&S.count(v[i]))qq[i]=1;
            else if (T.count(v[i])&&T.count(u[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;
}

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

    set<int>S,T;
    for(int i=0;i<n;++i){if(du[i]<dv[i])S.insert(i);if(dv[i]<du[i]) T.insert(i);}

    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:114:15: warning: 'e1' may be used uninitialized in this function [-Wmaybe-uninitialized]
  114 |     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
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 2560 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 2612 KB Output is correct
2 Correct 56 ms 3880 KB Output is correct
3 Correct 860 ms 14836 KB Output is correct
4 Correct 1063 ms 15024 KB Output is correct
5 Correct 1033 ms 14840 KB Output is correct
6 Correct 865 ms 14816 KB Output is correct
7 Correct 1097 ms 14592 KB Output is correct
8 Correct 1027 ms 14844 KB Output is correct
9 Correct 851 ms 14756 KB Output is correct
10 Correct 966 ms 14824 KB Output is correct
11 Correct 1309 ms 14348 KB Output is correct
12 Correct 1346 ms 14396 KB Output is correct
13 Correct 1126 ms 14000 KB Output is correct
14 Correct 1226 ms 13972 KB Output is correct

Subtask #3
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 39 ms 3772 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -

Subtask #4
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 2616 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 71 ms 3848 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 69 ms 3840 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -