oj.uz

Submission #829309

# Submission time Handle Problem Language Result Execution time Memory
829309 2023-08-18T08:40:32 Z vnm06 Highway Tolls (IOI18_highway) C++14
51 / 100
 110 ms 14608 KB 
#include<bits/stdc++.h>
#include "highway.h"
using namespace std;

int n, m;
vector<int> u, v;
vector<int> gr[90009];

vector<int> sp;
vector<int> vpr;
int par[90009], pos[90009];
bool used[90009];

void dfs1(int v)
{
    used[v]=1;
    int brs=gr[v].size();
    for(int i=0; i<brs; i++)
    {
        int nv=gr[v][i];
        if(used[nv]) continue;
        par[nv]=v;
        dfs1(nv);
    }
    sp.push_back(v);
}

void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B)
{
    n=N;
    u=U;
    v=V;
    int m = U.size();
    for(int i=0; i<m; i++)
    {
        gr[u[i]].push_back(v[i]);
        gr[v[i]].push_back(u[i]);
    }
    dfs1(0);
    vpr.resize(m);
    for(int i=0; i<m; i++) vpr[i]=0;
    ///cout<<1<<endl;
    long long expcost=ask(vpr);
    for(int i=0; i<m; i++)
    {
        if(par[u[i]]==v[i]) pos[u[i]]=i;
        else if(par[v[i]]==u[i]) pos[v[i]]=i;
    }
    int le=0, ri=n-2;
    ///cout<<1<<endl;
    while(le<ri)
    {
        int mid=(le+ri)/2;
        for(int i=0; i<m; i++) vpr[i]=0;
        for(int j=le; j<=mid; j++) vpr[pos[sp[j]]]=1;
        if(ask(vpr)!=expcost) ri=mid;
        else le=mid+1;
    }
    ///cout<<sp[le]<<endl;
    int v1=sp[le];
    sp.resize(0);
    for(int i=0; i<n; i++) par[i]=pos[i]=used[i]=0;
    vpr.resize(0);



    dfs1(v1);
    vpr.resize(m);
    for(int i=0; i<m; i++) vpr[i]=0;
    ///cout<<1<<endl;
    expcost=ask(vpr);
    for(int i=0; i<m; i++)
    {
        if(par[u[i]]==v[i]) pos[u[i]]=i;
        else if(par[v[i]]==u[i]) pos[v[i]]=i;
    }
    le=0, ri=n-2;
    while(le<ri)
    {
        int mid=(le+ri)/2;
        for(int i=0; i<m; i++) vpr[i]=0;
        for(int j=le; j<=mid; j++) vpr[pos[sp[j]]]=1;
        if(ask(vpr)!=expcost) ri=mid;
        else le=mid+1;
    }
    answer(v1, sp[le]);
}

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2384 KB Output is correct
2 Correct 10 ms 3180 KB Output is correct
3 Correct 76 ms 9144 KB Output is correct
4 Correct 82 ms 9068 KB Output is correct
5 Correct 93 ms 9064 KB Output is correct
6 Correct 81 ms 9088 KB Output is correct
7 Correct 106 ms 9080 KB Output is correct
8 Correct 94 ms 9064 KB Output is correct
9 Correct 100 ms 9072 KB Output is correct
10 Correct 78 ms 9064 KB Output is correct
11 Correct 82 ms 10336 KB Output is correct
12 Correct 81 ms 11088 KB Output is correct
13 Correct 75 ms 10472 KB Output is correct
14 Correct 103 ms 10564 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 3768 KB Output is correct
2 Correct 21 ms 5132 KB Output is correct
3 Correct 22 ms 6464 KB Output is correct
4 Correct 73 ms 14596 KB Output is correct
5 Correct 98 ms 14608 KB Output is correct
6 Correct 78 ms 14596 KB Output is correct
7 Correct 64 ms 14592 KB Output is correct
8 Correct 93 ms 14588 KB Output is correct
9 Correct 110 ms 14596 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2384 KB Output is correct
2 Correct 12 ms 3156 KB Output is correct
3 Correct 59 ms 7644 KB Output is correct
4 Correct 92 ms 9072 KB Output is correct
5 Correct 85 ms 9064 KB Output is correct
6 Correct 98 ms 9072 KB Output is correct
7 Correct 70 ms 9072 KB Output is correct
8 Correct 71 ms 9076 KB Output is correct
9 Correct 78 ms 9072 KB Output is correct
10 Correct 88 ms 9060 KB Output is correct
11 Correct 79 ms 10156 KB Output is correct
12 Correct 80 ms 11112 KB Output is correct
13 Correct 79 ms 10632 KB Output is correct
14 Correct 83 ms 10960 KB Output is correct
15 Correct 68 ms 9076 KB Output is correct
16 Correct 79 ms 9084 KB Output is correct
17 Correct 79 ms 10688 KB Output is correct
18 Correct 95 ms 10824 KB Output is correct
19 Correct 78 ms 9076 KB Output is correct
20 Correct 88 ms 11424 KB Output is correct
21 Correct 59 ms 9316 KB Output is correct
22 Correct 64 ms 9248 KB Output is correct
23 Correct 64 ms 9504 KB Output is correct
24 Correct 67 ms 9916 KB Output is correct
25 Correct 92 ms 14136 KB Output is correct

Subtask #5
0 / 18.0

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