oj.uz

Submission #1105235

# Submission time Handle Problem Language Result Execution time Memory
1105235 2024-10-25T20:07:49 Z alexander707070 Highway Tolls (IOI18_highway) C++14
51 / 100
 153 ms 18672 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,li[MAXN];

vector< pair<int,int> > v[MAXN],g[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);
    }
}

queue<int> q;

void bfs(int x){
    for(int i=0;i<g[x].size();i++){
        if(li[g[x][i].first])continue;

        li[g[x][i].first]=true;
        q.push(g[x][i].first);

        v[x].push_back(g[x][i]);
        v[g[x][i].first].push_back({x,g[x][i].second});
    }
}

void dobfs(int x){
    q.push(x);
    li[x]=true;

    while(!q.empty()){
        bfs(q.front());
        q.pop();
    }
}

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

    return ask(w);
}

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++){
        g[U[i-1]+1].push_back({V[i-1]+1,i-1});
        g[V[i-1]+1].push_back({U[i-1]+1,i-1});
    }

    w.resize(m);
    for(int i=0;i<m;i++)w[i]=1;
    long long path=ask(w);

    int l=-1,r=n,tt;
    while(l+1<r){
        tt=(l+r)/2;
        if(check(tt)==path){
            r=tt;
        }else{
            l=tt;
        }
    }

    r++;
    dobfs(r);

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

    l=-1; r=int(euler.size());
    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:19: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]
   19 |     for(int i=0;i<v[x].size();i++){
      |                 ~^~~~~~~~~~~~
highway.cpp: In function 'void dfss(int, int)':
highway.cpp:28: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]
   28 |     for(int i=0;i<v[x].size();i++){
      |                 ~^~~~~~~~~~~~
highway.cpp: In function 'void bfs(int)':
highway.cpp:39: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]
   39 |     for(int i=0;i<g[x].size();i++){
      |                 ~^~~~~~~~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5244 KB Output is correct
2 Correct 13 ms 6344 KB Output is correct
3 Correct 130 ms 15528 KB Output is correct
4 Correct 132 ms 15428 KB Output is correct
5 Correct 131 ms 15356 KB Output is correct
6 Correct 119 ms 15356 KB Output is correct
7 Correct 121 ms 15364 KB Output is correct
8 Correct 117 ms 15380 KB Output is correct
9 Correct 153 ms 15720 KB Output is correct
10 Correct 117 ms 15524 KB Output is correct
11 Correct 113 ms 15256 KB Output is correct
12 Correct 134 ms 15836 KB Output is correct
13 Correct 123 ms 15500 KB Output is correct
14 Correct 135 ms 15092 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 6480 KB Output is correct
2 Correct 23 ms 8004 KB Output is correct
3 Correct 41 ms 9640 KB Output is correct
4 Correct 124 ms 18556 KB Output is correct
5 Correct 96 ms 18496 KB Output is correct
6 Correct 99 ms 18472 KB Output is correct
7 Correct 102 ms 18672 KB Output is correct
8 Correct 99 ms 18520 KB Output is correct
9 Correct 104 ms 18584 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5200 KB Output is correct
2 Correct 13 ms 6224 KB Output is correct
3 Correct 90 ms 13276 KB Output is correct
4 Correct 124 ms 15896 KB Output is correct
5 Correct 133 ms 15520 KB Output is correct
6 Correct 132 ms 15328 KB Output is correct
7 Correct 144 ms 15460 KB Output is correct
8 Correct 117 ms 15348 KB Output is correct
9 Correct 132 ms 15696 KB Output is correct
10 Correct 121 ms 15408 KB Output is correct
11 Correct 151 ms 15196 KB Output is correct
12 Correct 129 ms 15760 KB Output is correct
13 Correct 126 ms 15496 KB Output is correct
14 Correct 125 ms 15848 KB Output is correct
15 Correct 124 ms 15348 KB Output is correct
16 Correct 109 ms 15428 KB Output is correct
17 Correct 146 ms 15672 KB Output is correct
18 Correct 133 ms 15384 KB Output is correct
19 Correct 134 ms 15348 KB Output is correct
20 Correct 140 ms 16236 KB Output is correct
21 Correct 107 ms 16348 KB Output is correct
22 Correct 103 ms 16364 KB Output is correct
23 Correct 108 ms 15872 KB Output is correct
24 Correct 116 ms 16364 KB Output is correct
25 Correct 151 ms 18144 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 17 ms 11344 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Runtime error 17 ms 11344 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -