oj.uz

Submission #934866

# Submission time Handle Problem Language Result Execution time Memory
934866 2024-02-28T05:53:36 Z sleepntsheep Highway Tolls (IOI18_highway) C++17
0 / 100
 10 ms 3672 KB 
#include "highway.h"
#include<bits/stdc++.h>
using namespace std;

int e[90001],d[90001],n,a,b;std::vector<int>u,v;std::vector<std::pair<int,int>>g[90001];

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_;
    int 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});

    {
        memset(d,63,sizeof d);
        queue<pair<int,int>>q;
        q.emplace(d[0]=0,0);
        while(q.size()){auto[c,u]=q.front();q.pop();for(auto [v,i]:g[u])if(d[v]>c+1)q.emplace(d[v]=c+1,v),e[v]=i;}
    }

    vector<int>c(n);
    iota(c.begin(),c.end(),0);
    sort(c.begin(),c.end(),[](int i,int v){return d[i]<d[v];});

    long long need;
    {vector<int>qq(m,1); need=ask(qq);}

    int z=0,l=0,r=n-1;
    while(l<=r){
        int y=(l+r)/2;
        vector<int>qq(m,0);
        for(int i=1;i<=y;++i)qq[e[i]]=1;
        if (ask(qq)==need)z=y,r=y-1;
        else l=y+1;
    }



    answer(0,z);
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2904 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 Incorrect 7 ms 3416 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2904 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 10 ms 3672 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 10 ms 3672 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -