oj.uz

Submission #829308

# Submission time Handle Problem Language Result Execution time Memory
829308 2023-08-18T08:37:39 Z vnm06 Highway Tolls (IOI18_highway) C++14
12 / 100
 106 ms 10916 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;
    answer(sp[le], 0);
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2408 KB Output is correct
2 Correct 2 ms 2384 KB Output is correct
3 Correct 1 ms 2312 KB Output is correct
4 Correct 1 ms 2384 KB Output is correct
5 Correct 1 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 1 ms 2384 KB Output is correct
2 Correct 8 ms 3152 KB Output is correct
3 Correct 88 ms 9196 KB Output is correct
4 Correct 89 ms 9080 KB Output is correct
5 Correct 102 ms 9084 KB Output is correct
6 Correct 89 ms 9092 KB Output is correct
7 Correct 86 ms 9068 KB Output is correct
8 Correct 75 ms 9080 KB Output is correct
9 Correct 61 ms 9108 KB Output is correct
10 Correct 69 ms 9048 KB Output is correct
11 Correct 100 ms 10324 KB Output is correct
12 Correct 66 ms 10916 KB Output is correct
13 Correct 106 ms 10444 KB Output is correct
14 Correct 65 ms 9904 KB Output is correct

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 3692 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 2 ms 2384 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 9 ms 3276 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 -