제출 #934925

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
934925		sleepntsheep	통행료 (IOI18_highway)	C++17	7 / 100	1346 ms	15024 KiB

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

컴파일 시 표준 에러 (stderr) 메시지

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
• Subtask 2: 7 / 7
• Subtask 3: 0 / 6
• Subtask 4: 0 / 33
• Subtask 5: 0 / 18
• Subtask 6: 0 / 31