oj.uz

Submission #1105238

# Submission time Handle Problem Language Result Execution time Memory
1105238 2024-10-25T20:18:08 Z alexander707070 Highway Tolls (IOI18_highway) C++14
51 / 100
 151 ms 24072 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]=1;
    for(int i=0;i<euler.size();i++)w[euler[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]=1;
    for(int i=0;i<euler.size();i++)w[euler[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++){
      |                     ~^~~~~~~~~~~~
highway.cpp: In function 'long long int pref(int)':
highway.cpp:75:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |     for(int i=0;i<euler.size();i++)w[euler[i]]=0;
      |                 ~^~~~~~~~~~~~~
highway.cpp: In function 'long long int pref2(int)':
highway.cpp:84:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |     for(int i=0;i<euler.size();i++)w[euler[i]]=0;
      |                 ~^~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 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 2 ms 10832 KB Output is correct
5 Correct 2 ms 10832 KB Output is correct
6 Correct 2 ms 10832 KB Output is correct
7 Correct 2 ms 10832 KB Output is correct
8 Correct 2 ms 10832 KB Output is correct
9 Correct 2 ms 11000 KB Output is correct
10 Correct 2 ms 10832 KB Output is correct
11 Correct 3 ms 11004 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 3 ms 10832 KB Output is correct
2 Correct 14 ms 11856 KB Output is correct
3 Correct 140 ms 20752 KB Output is correct
4 Correct 150 ms 20856 KB Output is correct
5 Correct 141 ms 20600 KB Output is correct
6 Correct 141 ms 20580 KB Output is correct
7 Correct 142 ms 20608 KB Output is correct
8 Correct 141 ms 20812 KB Output is correct
9 Correct 137 ms 20764 KB Output is correct
10 Correct 142 ms 20792 KB Output is correct
11 Correct 136 ms 20816 KB Output is correct
12 Correct 135 ms 21060 KB Output is correct
13 Correct 145 ms 20572 KB Output is correct
14 Correct 148 ms 20208 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 12112 KB Output is correct
2 Correct 23 ms 13644 KB Output is correct
3 Correct 34 ms 15032 KB Output is correct
4 Correct 102 ms 23796 KB Output is correct
5 Correct 100 ms 23724 KB Output is correct
6 Correct 101 ms 24072 KB Output is correct
7 Correct 105 ms 23668 KB Output is correct
8 Correct 107 ms 23756 KB Output is correct
9 Correct 104 ms 23844 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 11964 KB Output is correct
3 Correct 115 ms 18684 KB Output is correct
4 Correct 129 ms 20636 KB Output is correct
5 Correct 129 ms 20608 KB Output is correct
6 Correct 124 ms 20732 KB Output is correct
7 Correct 133 ms 20760 KB Output is correct
8 Correct 131 ms 20580 KB Output is correct
9 Correct 142 ms 20800 KB Output is correct
10 Correct 151 ms 20708 KB Output is correct
11 Correct 130 ms 20200 KB Output is correct
12 Correct 130 ms 21204 KB Output is correct
13 Correct 139 ms 21060 KB Output is correct
14 Correct 144 ms 21128 KB Output is correct
15 Correct 142 ms 20668 KB Output is correct
16 Correct 129 ms 20636 KB Output is correct
17 Correct 139 ms 20876 KB Output is correct
18 Correct 138 ms 20560 KB Output is correct
19 Correct 118 ms 20616 KB Output is correct
20 Correct 127 ms 21388 KB Output is correct
21 Correct 105 ms 21576 KB Output is correct
22 Correct 113 ms 21772 KB Output is correct
23 Correct 118 ms 21204 KB Output is correct
24 Correct 117 ms 21348 KB Output is correct
25 Correct 143 ms 23560 KB Output is correct

Subtask #5
0 / 18.0

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