oj.uz

Submission #1105214

# Submission time Handle Problem Language Result Execution time Memory
1105214 2024-10-25T18:08:16 Z alexander707070 Highway Tolls (IOI18_highway) C++14
5 / 100
 320 ms 262144 KB 
#include<bits/stdc++.h>
#define MAXN 100007
#include "highway.h"

using namespace std;

int n,m,dep[MAXN],from,to,st,et,parent[MAXN];
bool ok;
vector< pair<int,int> > v[MAXN];
vector<int> euler,euler2;
vector<int> w;

void dfs(int x,int p){

    dep[x]=dep[p]+1;
    parent[x]=p;

    for(int i=0;i<v[x].size();i++){
        if(v[x][i].first==p)continue;

        euler.push_back(v[x][i].second);
        dfs(v[x][i].first,x);
    }
}

void dfss(int x,int p){


    for(int i=0;i<v[x].size();i++){
        if(v[x][i].first==p)continue;

        euler2.push_back(v[x][i].second);
        dfss(v[x][i].first,x);
    }
}

int pref(int x){
    for(int i=0;i<=x;i++)w[euler[i]]=1;
    for(int i=x+1;i<m;i++)w[euler[i]]=0;

    return ask(w);
}

int pref2(int x){
    for(int i=0;i<=x;i++)w[euler2[i]]=1;
    for(int i=x+1;i<m;i++)w[euler2[i]]=0;

    return ask(w);
}

void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {

    n=N; m=int(U.size());
    for(int i=1;i<=m;i++){
        v[U[i-1]+1].push_back({V[i-1]+1,i-1});
        v[V[i-1]+1].push_back({U[i-1]+1,i-1});
    }

    dfs(1,0);
    for(int i=1;i<=n;i++){
        reverse(v[i].begin(),v[i].end());
    }
    dfss(1,0);
    
    w.resize(m);
    for(int i=0;i<m;i++)w[i]=1;

    long long path=ask(w);

    int l=-1,r=int(euler.size()),tt;
    while(l+1<r){
        tt=(l+r)/2;
        if(pref(tt)==path){
            r=tt;
        }else{
            l=tt;
        }
    }
    to=r;

    l=-1; r=int(euler2.size());
    while(l+1<r){
        tt=(l+r)/2;
        if(pref2(tt)==path){
            r=tt;
        }else{
            l=tt;
        }
    }
    from=r;

    st=euler2[from]; et=euler[to];

    if(st==et){
        if(dep[U[st]+1]>dep[V[st]+1])swap(U[st],V[st]);

        U[st]++;
        for(int i=0;i<path/B-1;i++)U[st]=parent[U[st]];
        U[st]--;

        answer(U[st],V[st]);
        return;
    }

    if(dep[U[st]+1]>dep[V[st]+1])swap(U[st],V[st]);
    if(dep[U[et]+1]>dep[V[et]+1])swap(U[et],V[et]);

    answer(V[st],V[et]);

    return;
}

Compilation message

highway.cpp: In function 'void dfs(int, int)':
highway.cpp:18:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |     for(int i=0;i<v[x].size();i++){
      |                 ~^~~~~~~~~~~~
highway.cpp: In function 'void dfss(int, int)':
highway.cpp:29:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |     for(int i=0;i<v[x].size();i++){
      |                 ~^~~~~~~~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2640 KB Output is correct
2 Correct 11 ms 3408 KB Output is correct
3 Correct 102 ms 9908 KB Output is correct
4 Correct 107 ms 9636 KB Output is correct
5 Correct 102 ms 9452 KB Output is correct
6 Correct 121 ms 9680 KB Output is correct
7 Correct 107 ms 9460 KB Output is correct
8 Correct 102 ms 9772 KB Output is correct
9 Correct 112 ms 9472 KB Output is correct
10 Correct 104 ms 9468 KB Output is correct
11 Correct 116 ms 9948 KB Output is correct
12 Correct 125 ms 10388 KB Output is correct
13 Correct 119 ms 10496 KB Output is correct
14 Incorrect 103 ms 9616 KB Output is incorrect: {s, t} is wrong.
15 Halted 0 ms 0 KB -

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 3920 KB Output is correct
2 Correct 25 ms 4944 KB Output is correct
3 Correct 30 ms 6108 KB Output is correct
4 Correct 90 ms 13132 KB Output is correct
5 Correct 82 ms 13132 KB Output is correct
6 Correct 84 ms 13136 KB Output is correct
7 Correct 87 ms 13324 KB Output is correct
8 Correct 89 ms 13148 KB Output is correct
9 Incorrect 84 ms 13136 KB Output is incorrect: {s, t} is wrong.
10 Halted 0 ms 0 KB -

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2640 KB Output is correct
2 Correct 13 ms 3388 KB Output is correct
3 Correct 82 ms 8028 KB Output is correct
4 Correct 109 ms 9456 KB Output is correct
5 Correct 128 ms 9644 KB Output is correct
6 Correct 129 ms 9452 KB Output is correct
7 Correct 104 ms 9460 KB Output is correct
8 Correct 109 ms 9460 KB Output is correct
9 Incorrect 117 ms 9700 KB Output is incorrect: {s, t} is wrong.
10 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 320 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Runtime error 294 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -