oj.uz

Submission #995516

# Submission time Handle Problem Language Result Execution time Memory
995516 2024-06-09T08:33:43 Z hirayuu_oj Highway Tolls (IOI18_highway) C++17
51 / 100
 85 ms 10240 KB 
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
#define rep2(i,l,r) for(int i=(l); i<(r); i++)
#define all(x) x.begin(),x.end()
using ll=long long;
ll LINF=(1LL<<61)-1;
ll MINF=1LL<<40;
int INF=INT_MAX>>1;

template<class S>
void out_vector(vector<S> v){
    for(S i:v)cerr<<i<<" ";
    cerr<<"\n";
}
#include "highway.h"

void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
    int M=U.size();
    ll dist=ask(vector<int>(M,0))/A;
    int ok=0,ng=M;
    while(ng-ok>1){
        int mid=(ok+ng)/2;
        vector<int> ques(M,0);
        rep2(i,ok,mid)ques[i]=1;
        if(ask(ques)==dist*A){
            ok=mid;
        }
        else{
            ng=mid;
        }
    }
    vector<vector<pair<int,int>>> tree(N);
    rep(i,N){
        if(i!=ok){
            tree[U[i]].emplace_back(V[i],i);
            tree[V[i]].emplace_back(U[i],i);
        }
    }
    int curs=U[ok],curt=V[ok];
    vector<int> sdis(N,-1);
    vector<int> par(N,-1);
    vector<int> which(N,-1);
    sdis[curs]=0;
    sdis[curt]=0;
    int sad;
    {
        stack<int> vert;
        vert.push(curt);
        vert.push(curs);
        vector<int> ques(M,0);
        int flg=1;
        while(!vert.empty()){
            int pos=vert.top();
            if(pos==curt)flg=0;
            which[pos]=flg;
            vert.pop();
            for(auto &[t,i]:tree[pos]){
                if(sdis[t]==-1){
                    ques[i]=flg;
                    par[t]=i;
                    sdis[t]=sdis[pos]+1;
                    vert.push(t);
                }
            }
        }
        sad=(ask(ques)-dist*A)/(B-A);
        vector<int> kouho;
        rep(i,N){
            if(which[i]==1&&sad==sdis[i]){
                kouho.emplace_back(i);
            }
        }
        ok=0,ng=kouho.size();
        while(ng-ok>1){
            int mid=(ok+ng)/2;
            vector<int> ques(M,0);
            rep2(i,ok,mid)ques[par[kouho[i]]]=1;
            if(ask(ques)==dist*A){
                ok=mid;
            }
            else{
                ng=mid;
            }
        }
        curs=kouho[ok];
    }
    {
        sad=dist-1-sad;
        vector<int> kouho;
        rep(i,N){
            if(which[i]==0&&sad==sdis[i]){
                kouho.emplace_back(i);
            }
        }
        ok=0,ng=kouho.size();
        while(ng-ok>1){
            int mid=(ok+ng)/2;
            vector<int> ques(M,0);
            rep2(i,ok,mid)ques[par[kouho[i]]]=1;
            if(ask(ques)==dist*A){
                ok=mid;
            }
            else{
                ng=mid;
            }
        }
        curt=kouho[ok];
    }
    answer(curs,curt);
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 1 ms 344 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 368 KB Output is correct
2 Correct 7 ms 1368 KB Output is correct
3 Correct 75 ms 9196 KB Output is correct
4 Correct 74 ms 8940 KB Output is correct
5 Correct 76 ms 8948 KB Output is correct
6 Correct 68 ms 8588 KB Output is correct
7 Correct 71 ms 9180 KB Output is correct
8 Correct 69 ms 8960 KB Output is correct
9 Correct 85 ms 8932 KB Output is correct
10 Correct 72 ms 8740 KB Output is correct
11 Correct 68 ms 8168 KB Output is correct
12 Correct 74 ms 8440 KB Output is correct
13 Correct 72 ms 8184 KB Output is correct
14 Correct 70 ms 8412 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1112 KB Output is correct
2 Correct 14 ms 2116 KB Output is correct
3 Correct 20 ms 2904 KB Output is correct
4 Correct 60 ms 8176 KB Output is correct
5 Correct 59 ms 7932 KB Output is correct
6 Correct 55 ms 8072 KB Output is correct
7 Correct 60 ms 8176 KB Output is correct
8 Correct 59 ms 8160 KB Output is correct
9 Correct 61 ms 8192 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 7 ms 1272 KB Output is correct
3 Correct 53 ms 6848 KB Output is correct
4 Correct 71 ms 8848 KB Output is correct
5 Correct 72 ms 8928 KB Output is correct
6 Correct 65 ms 8676 KB Output is correct
7 Correct 75 ms 8496 KB Output is correct
8 Correct 68 ms 8928 KB Output is correct
9 Correct 70 ms 9180 KB Output is correct
10 Correct 78 ms 9216 KB Output is correct
11 Correct 69 ms 8312 KB Output is correct
12 Correct 66 ms 8072 KB Output is correct
13 Correct 65 ms 8428 KB Output is correct
14 Correct 70 ms 8180 KB Output is correct
15 Correct 70 ms 8676 KB Output is correct
16 Correct 68 ms 8672 KB Output is correct
17 Correct 72 ms 8308 KB Output is correct
18 Correct 64 ms 8416 KB Output is correct
19 Correct 79 ms 8912 KB Output is correct
20 Correct 73 ms 8120 KB Output is correct
21 Correct 62 ms 9632 KB Output is correct
22 Correct 65 ms 10104 KB Output is correct
23 Correct 68 ms 9688 KB Output is correct
24 Correct 79 ms 10240 KB Output is correct
25 Correct 76 ms 8936 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 10 ms 2392 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Runtime error 8 ms 2384 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -