답안 #934901

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
934901 2024-02-28T06:54:23 Z sleepntsheep 통행료 (IOI18_highway) C++17
6 / 100
140 ms 16532 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);for(int i=0;i<n;++i)if(~e[i])qq[e[i]]=1;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,0);
        for(int i=1;i<=y;++i)if(~e[c[i]])qq[e[c[i]]]=1;
        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 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]=a;else qq[i]=b;
        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;
        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]);
        vector<int> test(n);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});

    if(a==1&&b==2)return sub5();
    sub1234();

}

Compilation message

highway.cpp: In lambda function:
highway.cpp:55:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   55 |         if(ask(qq)&1)return 1;return 0;
      |         ^~
highway.cpp:55:31: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   55 |         if(ask(qq)&1)return 1;return 0;
      |                               ^~~~~~
highway.cpp: In function 'void sub5()':
highway.cpp:70:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |         for(int i=0;i<gs.size()/2;++i)n1.push_back(gs[i]);
      |                     ~^~~~~~~~~~~~
highway.cpp:71:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |         for(int i=gs.size()/2;i<gs.size();++i)n2.push_back(gs[i]);
      |                               ~^~~~~~~~~~
highway.cpp:79:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |         for(int i=0;i<gt.size()/2;++i)n1.push_back(gt[i]);
      |                     ~^~~~~~~~~~~~
highway.cpp:80:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |         for(int i=gt.size()/2;i<gt.size();++i)n2.push_back(gt[i]);
      |                               ~^~~~~~~~~~
highway.cpp:50:9: warning: unused variable 'l' [-Wunused-variable]
   50 |     int l=0,r=n-1;
      |         ^
highway.cpp:50:13: warning: unused variable 'r' [-Wunused-variable]
   50 |     int l=0,r=n-1;
      |             ^
highway.cpp: In function 'void sub1234()':
highway.cpp:44:15: warning: 'e1' may be used uninitialized in this function [-Wmaybe-uninitialized]
   44 |     int p=u[e1],q=v[e1],s=sub12(p,e1),t=sub12(q,e1);
      |               ^
# 결과 실행 시간 메모리 Grader output
1 Runtime error 3 ms 4864 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2620 KB Output is correct
2 Correct 13 ms 3348 KB Output is correct
3 Correct 89 ms 9892 KB Output is correct
4 Correct 87 ms 9848 KB Output is correct
5 Correct 104 ms 9796 KB Output is correct
6 Correct 94 ms 9636 KB Output is correct
7 Correct 140 ms 10120 KB Output is correct
8 Correct 111 ms 9668 KB Output is correct
9 Correct 103 ms 9688 KB Output is correct
10 Correct 124 ms 9896 KB Output is correct
11 Runtime error 105 ms 16532 KB Execution killed with signal 11
12 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 3260 KB Output is correct
2 Correct 28 ms 4116 KB Output is correct
3 Correct 34 ms 4572 KB Output is correct
4 Correct 72 ms 9068 KB Output is correct
5 Correct 66 ms 9020 KB Output is correct
6 Correct 61 ms 9336 KB Output is correct
7 Correct 65 ms 9044 KB Output is correct
8 Correct 70 ms 9044 KB Output is correct
9 Correct 74 ms 9128 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Runtime error 4 ms 4920 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Runtime error 12 ms 6528 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 13 ms 3400 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -