oj.uz

Submission #978689

# Submission time Handle Problem Language Result Execution time Memory
978689 2024-05-09T14:01:20 Z bachhoangxuan Highway Tolls (IOI18_highway) C++17
0 / 100
 16 ms 4328 KB 
#include "highway.h"
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+5;
#define pii pair<int,int>
#define fi first
#define se second

int dd[2][maxn],f[2][maxn];
vector<pii> edge[maxn];

void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
    vector<int> S(2),T(2);
    int M=(int)U.size();
    for(int i=0;i<M;i++){
        edge[U[i]].push_back({V[i],i});
        edge[V[i]].push_back({U[i],i});
    }

    vector<int> w(M,0);
    int dist=ask(w);
    int l=1,r=M;
    while(l<r){
        int mid=(l+r+1)>>1;
        w.assign(M,0);
        for(int i=0;i<mid;i++) w[i]=1;
        if(ask(w)!=dist) r=mid-1;
        else l=mid;
    }
    S[0]=U[l-1],S[1]=V[l-1];
    for(int i=0;i<=1;i++){
        queue<int> qq;
        for(int u=0;u<N;u++) dd[i][u]=f[i][u]=-1;
        dd[i][S[i]]=0;qq.push(S[i]);
        while(!qq.empty()){
            int u=qq.front();qq.pop();
            for(auto [v,id]:edge[u]) if(dd[i][v]!=-1){
                dd[i][v]=dd[i][u]+1;
                f[i][v]=id;
                qq.push(v);
            }
        }
    }
    vector<vector<int>> cc(2);
    for(int u=0;u<N;u++){
        if(dd[0][u]<dd[1][u]) cc[0].push_back(u);
        else cc[1].push_back(u);
    }

    for(int i=0;i<=1;i++){
        sort(cc[i].begin(),cc[i].end(),[&](int x,int y){
            return dd[i][x]<dd[i][y];
        });
        T[i]=cc[i][0];
        l=1,r=(int)cc[i].size()-1;
        while(l<=r){
            int mid=(l+r)>>1;
            w.assign(M,0);
            for(int j=mid;j<(int)cc[i].size();j++) for(auto [v,id]:edge[cc[i][j]]) w[id]=1;
            if(ask(w)!=dist) T[i]=cc[i][mid],l=mid+1;
            else r=mid-1;
        }
    }
    answer(T[0],T[1]);
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2800 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2852 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 3620 KB Output is correct
2 Incorrect 16 ms 4328 KB Output is incorrect: {s, t} is wrong.
3 Halted 0 ms 0 KB -

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2852 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 14 ms 3704 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 3688 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -