oj.uz

Submission #854350

# Submission time Handle Problem Language Result Execution time Memory
854350 2023-09-27T02:37:34 Z abcvuitunggio Highway Tolls (IOI18_highway) C++17
0 / 100
 117 ms 10460 KB 
#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
int M,d[90001][2],type[90001],S,T;
vector <int> ke[90001];
vector <pair <int, int>> a,b;
queue <int> q;
void bfs(int s, int i){
    d[s][i]=0;
    q.push(s);
    while (!q.empty()){
        int u=q.front();
        q.pop();
        for (int v:ke[u])
            if (d[v][i]==-1){
                d[v][i]=d[u][i]+1;
                q.push(v);
            }
    }
}
void find_pair(int N, vector<int> U, vector<int> V, int A, int B){
    M=U.size();
    memset(d,-1,sizeof(d));
    vector <int> w(M,0);
    int dist=ask(w);
    int l=0,r=M-1,kq=-1;
    while (l<=r){
        int mid=(l+r)>>1;
        for (int i=0;i<=mid;i++)
            w[i]=1;
        if (ask(w)>dist){
            kq=mid;
            r=mid-1;
        }
        else
            l=mid+1;
        for (int i=0;i<=mid;i++)
            w[i]=0;
    }
    for (int i=kq+1;i<M;i++){
        ke[U[i]].push_back(V[i]);
        ke[V[i]].push_back(U[i]);
    }
    bfs(U[kq],0);
    bfs(V[kq],1);
    for (int i=0;i<N;i++){
        if (d[i][0]==-1&&d[i][1]==-1)
            continue;
        if (d[i][1]==-1||d[i][1]>d[i][0]+A)
            type[i]=1;
        if (d[i][0]==-1||d[i][0]>d[i][1]+A)
            type[i]=2;
    }
    for (int i=kq+1;i<M;i++){
        if (type[U[i]]==1&&type[V[i]]==1)
            a.emplace_back(max(d[U[i]][0],d[V[i]][0]),i);
        if (type[U[i]]==2&&type[V[i]]==2)
            b.emplace_back(max(d[U[i]][1],d[V[i]][1]),i);
    }
    sort(a.begin(),a.end());
    sort(b.begin(),b.end());
    int tmp=kq;
    l=0,r=a.size()-1,kq=-1;
    while (l<=r){
        int mid=(l+r)>>1;
        for (int i=mid;i<a.size();i++)
            w[a[i].second]=1;
        if (ask(w)>dist){
            kq=a[mid].second;
            l=mid+1;
        }
        else
            r=mid-1;
        for (int i=mid;i<a.size();i++)
            w[a[i].second]=0;
    }
    S=(kq==-1?U[tmp]:(d[U[kq]][0]>d[V[kq]][0]?U[kq]:V[kq]));
    l=0,r=b.size()-1,kq=-1;
    while (l<=r){
        int mid=(l+r)>>1;
        for (int i=mid;i<b.size();i++)
            w[b[i].second]=1;
        if (ask(w)>dist){
            kq=b[mid].second;
            l=mid+1;
        }
        else
            r=mid-1;
        for (int i=mid;i<b.size();i++)
            w[b[i].second]=0;
    }
    T=(kq==-1?V[tmp]:(d[U[kq]][1]>d[V[kq]][1]?U[kq]:V[kq]));
    answer(S,T);
}

Compilation message

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:66:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |         for (int i=mid;i<a.size();i++)
      |                        ~^~~~~~~~~
highway.cpp:74:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |         for (int i=mid;i<a.size();i++)
      |                        ~^~~~~~~~~
highway.cpp:81:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |         for (int i=mid;i<b.size();i++)
      |                        ~^~~~~~~~~
highway.cpp:89:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |         for (int i=mid;i<b.size();i++)
      |                        ~^~~~~~~~~

Subtask #1
0 / 5.0

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

Subtask #2
0 / 7.0

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

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4016 KB Output is correct
2 Correct 14 ms 4788 KB Output is correct
3 Correct 20 ms 4116 KB Output is correct
4 Correct 62 ms 8148 KB Output is correct
5 Correct 61 ms 7704 KB Output is correct
6 Correct 61 ms 8824 KB Output is correct
7 Correct 54 ms 5408 KB Output is correct
8 Correct 64 ms 8232 KB Output is correct
9 Incorrect 60 ms 9336 KB Output is incorrect: {s, t} is wrong.
10 Halted 0 ms 0 KB -

Subtask #4
0 / 33.0

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

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 4020 KB Output is correct
2 Correct 12 ms 4020 KB Output is correct
3 Correct 99 ms 9784 KB Output is correct
4 Correct 113 ms 9284 KB Output is correct
5 Correct 116 ms 10100 KB Output is correct
6 Correct 117 ms 10460 KB Output is correct
7 Correct 116 ms 9932 KB Output is correct
8 Incorrect 95 ms 9948 KB Output is incorrect: {s, t} is wrong.
9 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 4180 KB Output is correct
2 Correct 10 ms 4120 KB Output is correct
3 Correct 82 ms 8952 KB Output is correct
4 Correct 81 ms 8988 KB Output is correct
5 Correct 97 ms 8868 KB Output is correct
6 Incorrect 98 ms 9264 KB Output is incorrect: {s, t} is wrong.
7 Halted 0 ms 0 KB -