oj.uz

Submission #1105241

# Submission time Handle Problem Language Result Execution time Memory
1105241 2024-10-25T20:28:27 Z alexander707070 Highway Tolls (IOI18_highway) C++14
6 / 100
 192 ms 23904 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());

    for(int i=0;i<euler2.size();i++){
        if(euler2[i]==euler[r]){
            l=i-1; break;
        }
    }

    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++){
      |                     ~^~~~~~~~~~~~
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:132:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  132 |     for(int i=0;i<euler2.size();i++){
      |                 ~^~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10832 KB Output is correct
2 Incorrect 3 ms 10832 KB Output is incorrect: {s, t} is wrong.
3 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 11108 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -

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 13768 KB Output is correct
3 Correct 34 ms 14920 KB Output is correct
4 Correct 100 ms 23840 KB Output is correct
5 Correct 95 ms 23752 KB Output is correct
6 Correct 99 ms 23904 KB Output is correct
7 Correct 105 ms 23764 KB Output is correct
8 Correct 117 ms 23900 KB Output is correct
9 Correct 103 ms 23888 KB Output is correct

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 10832 KB Output is correct
2 Correct 13 ms 11856 KB Output is correct
3 Correct 123 ms 18552 KB Output is correct
4 Correct 125 ms 20616 KB Output is correct
5 Correct 121 ms 20856 KB Output is correct
6 Correct 122 ms 20756 KB Output is correct
7 Correct 132 ms 20676 KB Output is correct
8 Correct 133 ms 20760 KB Output is correct
9 Correct 137 ms 20576 KB Output is correct
10 Correct 138 ms 20984 KB Output is correct
11 Correct 151 ms 20188 KB Output is correct
12 Correct 157 ms 21212 KB Output is correct
13 Correct 127 ms 20704 KB Output is correct
14 Correct 136 ms 21128 KB Output is correct
15 Correct 132 ms 20712 KB Output is correct
16 Correct 137 ms 20692 KB Output is correct
17 Correct 137 ms 20892 KB Output is correct
18 Correct 128 ms 20640 KB Output is correct
19 Correct 130 ms 20676 KB Output is correct
20 Correct 125 ms 21472 KB Output is correct
21 Incorrect 102 ms 21584 KB Output is incorrect: {s, t} is wrong.
22 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 11856 KB Output is correct
2 Correct 17 ms 11856 KB Output is correct
3 Correct 156 ms 21016 KB Output is correct
4 Incorrect 192 ms 21352 KB Output is incorrect: {s, t} is wrong.
5 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 11868 KB Output is correct
2 Correct 16 ms 11892 KB Output is correct
3 Incorrect 136 ms 21280 KB Output is incorrect: {s, t} is wrong.
4 Halted 0 ms 0 KB -