oj.uz

Submission #1105237

# Submission time Handle Problem Language Result Execution time Memory
1105237 2024-10-25T20:16:40 Z alexander707070 Highway Tolls (IOI18_highway) C++14
51 / 100
 171 ms 23924 KB 
#include<bits/stdc++.h>
#define MAXN 200007

#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<m;i++)w[i]=0;

    for(int y=1;y<=x;y++){
        for(int i=0;i<g[y].size();i++){
            w[g[y][i].second]=1;
        }
    }

    return ask(w);
}

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

    return ask(w);
}

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

    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=0,r=n+1,tt;
    while(l+1<r){
        tt=(l+r)/2;
        if(check(tt)==path){
            r=tt;
        }else{
            l=tt;
        }
    }

    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:20: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]
   20 |     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++){
      |                 ~^~~~~~~~~~~~
highway.cpp: In function 'void bfs(int)':
highway.cpp:40: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]
   40 |     for(int i=0;i<g[x].size();i++){
      |                 ~^~~~~~~~~~~~
highway.cpp: In function 'long long int check(int)':
highway.cpp:65:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |         for(int i=0;i<g[y].size();i++){
      |                     ~^~~~~~~~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 10832 KB Output is correct
2 Correct 14 ms 12216 KB Output is correct
3 Correct 151 ms 20952 KB Output is correct
4 Correct 171 ms 20544 KB Output is correct
5 Correct 128 ms 20600 KB Output is correct
6 Correct 139 ms 20576 KB Output is correct
7 Correct 133 ms 20880 KB Output is correct
8 Correct 137 ms 20552 KB Output is correct
9 Correct 125 ms 20700 KB Output is correct
10 Correct 129 ms 20668 KB Output is correct
11 Correct 135 ms 20772 KB Output is correct
12 Correct 131 ms 21120 KB Output is correct
13 Correct 131 ms 20872 KB Output is correct
14 Correct 127 ms 20284 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 12280 KB Output is correct
2 Correct 29 ms 13636 KB Output is correct
3 Correct 34 ms 15120 KB Output is correct
4 Correct 101 ms 23768 KB Output is correct
5 Correct 99 ms 23692 KB Output is correct
6 Correct 99 ms 23820 KB Output is correct
7 Correct 119 ms 23924 KB Output is correct
8 Correct 101 ms 23864 KB Output is correct
9 Correct 97 ms 23828 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 10832 KB Output is correct
2 Correct 14 ms 11968 KB Output is correct
3 Correct 97 ms 18680 KB Output is correct
4 Correct 119 ms 20648 KB Output is correct
5 Correct 122 ms 20736 KB Output is correct
6 Correct 120 ms 20612 KB Output is correct
7 Correct 124 ms 20676 KB Output is correct
8 Correct 120 ms 20580 KB Output is correct
9 Correct 131 ms 20552 KB Output is correct
10 Correct 133 ms 20560 KB Output is correct
11 Correct 134 ms 20088 KB Output is correct
12 Correct 135 ms 21216 KB Output is correct
13 Correct 132 ms 20884 KB Output is correct
14 Correct 131 ms 21024 KB Output is correct
15 Correct 126 ms 20668 KB Output is correct
16 Correct 124 ms 20616 KB Output is correct
17 Correct 135 ms 20820 KB Output is correct
18 Correct 127 ms 20552 KB Output is correct
19 Correct 142 ms 20668 KB Output is correct
20 Correct 145 ms 21340 KB Output is correct
21 Correct 116 ms 21928 KB Output is correct
22 Correct 130 ms 21736 KB Output is correct
23 Correct 116 ms 21548 KB Output is correct
24 Correct 137 ms 21596 KB Output is correct
25 Correct 144 ms 23604 KB Output is correct

Subtask #5
0 / 18.0

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