oj.uz

Submission #934871

# Submission time Handle Problem Language Result Execution time Memory
934871 2024-02-28T05:58:43 Z sleepntsheep Highway Tolls (IOI18_highway) C++17
12 / 100
 120 ms 9988 KB 
#include "highway.h"
#include<bits/stdc++.h>
using namespace std;

int e[90001],d[90001],n,m,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_;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[c[i]]]=1;
        if (ask(qq)==need)z=c[y],r=y-1;
        else l=y+1;
    }

    answer(0,z);
}

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2904 KB Output is correct
2 Correct 10 ms 3672 KB Output is correct
3 Correct 73 ms 9764 KB Output is correct
4 Correct 76 ms 9524 KB Output is correct
5 Correct 74 ms 9988 KB Output is correct
6 Correct 75 ms 9508 KB Output is correct
7 Correct 72 ms 9524 KB Output is correct
8 Correct 77 ms 9980 KB Output is correct
9 Correct 69 ms 9704 KB Output is correct
10 Correct 97 ms 9524 KB Output is correct
11 Correct 83 ms 9112 KB Output is correct
12 Correct 82 ms 8912 KB Output is correct
13 Correct 76 ms 9356 KB Output is correct
14 Correct 120 ms 8892 KB Output is correct

Subtask #3
0 / 6.0

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