oj.uz

Submission #1105231

# Submission time Handle Problem Language Result Execution time Memory
1105231 2024-10-25T19:46:09 Z alexander707070 Highway Tolls (IOI18_highway) C++14
51 / 100
 326 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);
    }
}

long long 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);
}

long long 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:27: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]
   27 |     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 1 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 2640 KB Output is correct
8 Correct 1 ms 2640 KB Output is correct
9 Correct 2 ms 2640 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
7.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 109 ms 9456 KB Output is correct
4 Correct 110 ms 9464 KB Output is correct
5 Correct 99 ms 9524 KB Output is correct
6 Correct 108 ms 9460 KB Output is correct
7 Correct 110 ms 9464 KB Output is correct
8 Correct 117 ms 9472 KB Output is correct
9 Correct 118 ms 9456 KB Output is correct
10 Correct 102 ms 9676 KB Output is correct
11 Correct 110 ms 9928 KB Output is correct
12 Correct 126 ms 10384 KB Output is correct
13 Correct 114 ms 10024 KB Output is correct
14 Correct 108 ms 9616 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 3920 KB Output is correct
2 Correct 20 ms 4944 KB Output is correct
3 Correct 33 ms 6208 KB Output is correct
4 Correct 86 ms 13132 KB Output is correct
5 Correct 115 ms 13124 KB Output is correct
6 Correct 89 ms 13616 KB Output is correct
7 Correct 86 ms 13160 KB Output is correct
8 Correct 85 ms 13132 KB Output is correct
9 Correct 87 ms 14020 KB Output is correct

Subtask #4
33.0 / 33.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 77 ms 8028 KB Output is correct
4 Correct 114 ms 9456 KB Output is correct
5 Correct 127 ms 9464 KB Output is correct
6 Correct 106 ms 9460 KB Output is correct
7 Correct 105 ms 9464 KB Output is correct
8 Correct 132 ms 9448 KB Output is correct
9 Correct 93 ms 9460 KB Output is correct
10 Correct 104 ms 10220 KB Output is correct
11 Correct 122 ms 9544 KB Output is correct
12 Correct 104 ms 10600 KB Output is correct
13 Correct 107 ms 10100 KB Output is correct
14 Correct 116 ms 10404 KB Output is correct
15 Correct 99 ms 9848 KB Output is correct
16 Correct 98 ms 9464 KB Output is correct
17 Correct 111 ms 10208 KB Output is correct
18 Correct 107 ms 9908 KB Output is correct
19 Correct 105 ms 9484 KB Output is correct
20 Correct 109 ms 10760 KB Output is correct
21 Correct 100 ms 9660 KB Output is correct
22 Correct 88 ms 9664 KB Output is correct
23 Correct 88 ms 9660 KB Output is correct
24 Correct 96 ms 10016 KB Output is correct
25 Correct 128 ms 12528 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 326 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 307 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -