oj.uz

Submission #1105239

# Submission time Handle Problem Language Result Execution time Memory
1105239 2024-10-25T20:25:33 Z alexander707070 Highway Tolls (IOI18_highway) C++14
90 / 100
 223 ms 24760 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]=1;

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

    return ask(w);
}

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

    for(int i=0;i<=x;i++)w[euler[i]]=0;

    return ask(w);
}

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

    for(int i=0;i<=x;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]=0;
    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/A-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 4 ms 10832 KB Output is correct
3 Correct 3 ms 10884 KB Output is correct
4 Correct 3 ms 10832 KB Output is correct
5 Correct 3 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 3 ms 10832 KB Output is correct
10 Correct 3 ms 10832 KB Output is correct
11 Correct 2 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 3 ms 10832 KB Output is correct
2 Correct 14 ms 11964 KB Output is correct
3 Correct 141 ms 20624 KB Output is correct
4 Correct 148 ms 20548 KB Output is correct
5 Correct 135 ms 20704 KB Output is correct
6 Correct 146 ms 20764 KB Output is correct
7 Correct 144 ms 20700 KB Output is correct
8 Correct 150 ms 20752 KB Output is correct
9 Correct 131 ms 20608 KB Output is correct
10 Correct 134 ms 20696 KB Output is correct
11 Correct 151 ms 20644 KB Output is correct
12 Correct 131 ms 21148 KB Output is correct
13 Correct 135 ms 20932 KB Output is correct
14 Correct 124 ms 20192 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 22 ms 13752 KB Output is correct
3 Correct 32 ms 15168 KB Output is correct
4 Correct 97 ms 23840 KB Output is correct
5 Correct 90 ms 23768 KB Output is correct
6 Correct 124 ms 23656 KB Output is correct
7 Correct 100 ms 23772 KB Output is correct
8 Correct 123 ms 23724 KB Output is correct
9 Correct 120 ms 24760 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 17 ms 11848 KB Output is correct
3 Correct 101 ms 18552 KB Output is correct
4 Correct 131 ms 20628 KB Output is correct
5 Correct 138 ms 20660 KB Output is correct
6 Correct 128 ms 20644 KB Output is correct
7 Correct 135 ms 20988 KB Output is correct
8 Correct 131 ms 20624 KB Output is correct
9 Correct 159 ms 20848 KB Output is correct
10 Correct 132 ms 20608 KB Output is correct
11 Correct 130 ms 20296 KB Output is correct
12 Correct 130 ms 21160 KB Output is correct
13 Correct 140 ms 20868 KB Output is correct
14 Correct 137 ms 21168 KB Output is correct
15 Correct 129 ms 20720 KB Output is correct
16 Correct 115 ms 20768 KB Output is correct
17 Correct 134 ms 20912 KB Output is correct
18 Correct 143 ms 20468 KB Output is correct
19 Correct 146 ms 20620 KB Output is correct
20 Correct 127 ms 21464 KB Output is correct
21 Correct 133 ms 21580 KB Output is correct
22 Correct 112 ms 21580 KB Output is correct
23 Correct 111 ms 21144 KB Output is correct
24 Correct 104 ms 21604 KB Output is correct
25 Correct 131 ms 23436 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 11856 KB Output is correct
2 Correct 19 ms 12112 KB Output is correct
3 Correct 140 ms 21020 KB Output is correct
4 Correct 165 ms 21452 KB Output is correct
5 Correct 195 ms 22204 KB Output is correct
6 Correct 192 ms 22012 KB Output is correct
7 Correct 201 ms 22004 KB Output is correct
8 Correct 191 ms 22192 KB Output is correct
9 Correct 161 ms 17924 KB Output is correct
10 Correct 147 ms 18428 KB Output is correct
11 Correct 145 ms 19236 KB Output is correct
12 Correct 202 ms 20940 KB Output is correct
13 Correct 189 ms 21600 KB Output is correct
14 Correct 203 ms 21832 KB Output is correct
15 Correct 211 ms 21800 KB Output is correct
16 Correct 162 ms 19024 KB Output is correct
17 Correct 125 ms 21416 KB Output is correct
18 Correct 140 ms 21692 KB Output is correct
19 Correct 118 ms 21680 KB Output is correct
20 Correct 117 ms 21672 KB Output is correct
21 Correct 184 ms 22272 KB Output is correct

Subtask #6
21.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 11856 KB Output is correct
2 Correct 17 ms 12036 KB Output is correct
3 Partially correct 146 ms 20904 KB Output is partially correct
4 Partially correct 164 ms 21420 KB Output is partially correct
5 Correct 179 ms 21264 KB Output is correct
6 Correct 205 ms 22012 KB Output is correct
7 Correct 155 ms 20972 KB Output is correct
8 Partially correct 158 ms 21064 KB Output is partially correct
9 Partially correct 191 ms 21436 KB Output is partially correct
10 Correct 198 ms 22524 KB Output is correct
11 Correct 207 ms 22200 KB Output is correct
12 Correct 219 ms 22000 KB Output is correct
13 Correct 146 ms 19232 KB Output is correct
14 Correct 140 ms 18128 KB Output is correct
15 Correct 146 ms 19224 KB Output is correct
16 Correct 143 ms 18308 KB Output is correct
17 Correct 157 ms 19232 KB Output is correct
18 Correct 131 ms 18128 KB Output is correct
19 Correct 214 ms 21052 KB Output is correct
20 Correct 174 ms 21568 KB Output is correct
21 Correct 198 ms 21836 KB Output is correct
22 Correct 204 ms 22044 KB Output is correct
23 Partially correct 189 ms 21968 KB Output is partially correct
24 Partially correct 191 ms 21964 KB Output is partially correct
25 Correct 194 ms 21784 KB Output is correct
26 Partially correct 205 ms 21924 KB Output is partially correct
27 Correct 127 ms 21688 KB Output is correct
28 Partially correct 115 ms 21544 KB Output is partially correct
29 Partially correct 155 ms 21896 KB Output is partially correct
30 Partially correct 120 ms 21656 KB Output is partially correct
31 Partially correct 119 ms 21484 KB Output is partially correct
32 Partially correct 124 ms 21544 KB Output is partially correct
33 Partially correct 158 ms 22004 KB Output is partially correct
34 Partially correct 120 ms 21884 KB Output is partially correct
35 Partially correct 144 ms 21560 KB Output is partially correct
36 Partially correct 115 ms 21432 KB Output is partially correct
37 Correct 123 ms 21856 KB Output is correct
38 Partially correct 129 ms 21592 KB Output is partially correct
39 Correct 182 ms 22420 KB Output is correct
40 Partially correct 185 ms 22540 KB Output is partially correct
41 Correct 223 ms 22168 KB Output is correct
42 Correct 197 ms 22356 KB Output is correct