oj.uz

답안 #934926

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
934926 2024-02-28T07:59:17 Z sleepntsheep 통행료 (IOI18_highway) C++17
51 / 100
 1358 ms 15576 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(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.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
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2556 KB Output is correct
2 Correct 2 ms 2556 KB Output is correct
3 Correct 2 ms 2820 KB Output is correct
4 Correct 2 ms 2648 KB Output is correct
5 Correct 1 ms 2552 KB Output is correct
6 Correct 2 ms 2560 KB Output is correct
7 Correct 1 ms 2556 KB Output is correct
8 Correct 1 ms 2552 KB Output is correct
9 Correct 1 ms 2556 KB Output is correct
10 Correct 2 ms 2560 KB Output is correct
11 Correct 1 ms 2552 KB Output is correct
12 Correct 2 ms 2560 KB Output is correct

Subtask #2
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 2872 KB Output is correct
2 Correct 54 ms 3920 KB Output is correct
3 Correct 888 ms 15088 KB Output is correct
4 Correct 1143 ms 15280 KB Output is correct
5 Correct 1002 ms 15084 KB Output is correct
6 Correct 892 ms 14816 KB Output is correct
7 Correct 1072 ms 14836 KB Output is correct
8 Correct 1083 ms 14852 KB Output is correct
9 Correct 829 ms 14700 KB Output is correct
10 Correct 967 ms 14584 KB Output is correct
11 Correct 1358 ms 14404 KB Output is correct
12 Correct 1267 ms 14160 KB Output is correct
13 Correct 1191 ms 14252 KB Output is correct
14 Correct 1245 ms 14196 KB Output is correct

Subtask #3
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 43 ms 3788 KB Output is correct
2 Correct 82 ms 5100 KB Output is correct
3 Correct 135 ms 6196 KB Output is correct
4 Correct 558 ms 14192 KB Output is correct
5 Correct 572 ms 14676 KB Output is correct
6 Correct 588 ms 14160 KB Output is correct
7 Correct 479 ms 14204 KB Output is correct
8 Correct 554 ms 14704 KB Output is correct
9 Correct 470 ms 14140 KB Output is correct

Subtask #4
33.0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 2648 KB Output is correct
2 Correct 68 ms 3884 KB Output is correct
3 Correct 608 ms 11824 KB Output is correct
4 Correct 844 ms 15052 KB Output is correct
5 Correct 857 ms 14804 KB Output is correct
6 Correct 852 ms 14564 KB Output is correct
7 Correct 802 ms 15092 KB Output is correct
8 Correct 859 ms 14556 KB Output is correct
9 Correct 1258 ms 15044 KB Output is correct
10 Correct 1091 ms 14820 KB Output is correct
11 Correct 1100 ms 14240 KB Output is correct
12 Correct 1322 ms 14160 KB Output is correct
13 Correct 1238 ms 13908 KB Output is correct
14 Correct 1323 ms 14204 KB Output is correct
15 Correct 850 ms 15576 KB Output is correct
16 Correct 838 ms 15080 KB Output is correct
17 Correct 1198 ms 13948 KB Output is correct
18 Correct 1247 ms 14468 KB Output is correct
19 Correct 844 ms 14836 KB Output is correct
20 Correct 1288 ms 13952 KB Output is correct
21 Correct 611 ms 15176 KB Output is correct
22 Correct 563 ms 15436 KB Output is correct
23 Correct 849 ms 14800 KB Output is correct
24 Correct 850 ms 14712 KB Output is correct
25 Correct 1190 ms 14300 KB Output is correct

Subtask #5
0 / 18.0

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

Subtask #6
0 / 31.0

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