oj.uz

Submission #854351

# Submission time Handle Problem Language Result Execution time Memory
854351 2023-09-27T02:39:09 Z abcvuitunggio Highway Tolls (IOI18_highway) C++17
6 / 100
 178 ms 10228 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);
    long long 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 3372 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 14 ms 4104 KB Output is incorrect: {s, t} is wrong.
3 Halted 0 ms 0 KB -

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 3820 KB Output is correct
2 Correct 25 ms 4516 KB Output is correct
3 Correct 35 ms 4148 KB Output is correct
4 Correct 60 ms 7888 KB Output is correct
5 Correct 82 ms 7940 KB Output is correct
6 Correct 55 ms 8572 KB Output is correct
7 Correct 79 ms 5616 KB Output is correct
8 Correct 66 ms 7972 KB Output is correct
9 Correct 66 ms 6260 KB Output is correct

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 3388 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 14 ms 4020 KB Output is correct
2 Correct 11 ms 4028 KB Output is correct
3 Correct 101 ms 9532 KB Output is correct
4 Correct 105 ms 9108 KB Output is correct
5 Correct 107 ms 9404 KB Output is correct
6 Correct 175 ms 10228 KB Output is correct
7 Correct 130 ms 10152 KB Output is correct
8 Incorrect 142 ms 9880 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 11 ms 4180 KB Output is correct
2 Correct 18 ms 4108 KB Output is correct
3 Correct 80 ms 8732 KB Output is correct
4 Correct 117 ms 9208 KB Output is correct
5 Correct 84 ms 8884 KB Output is correct
6 Incorrect 178 ms 9500 KB Output is incorrect: {s, t} is wrong.
7 Halted 0 ms 0 KB -