oj.uz

Submission #854354

# Submission time Handle Problem Language Result Execution time Memory
854354 2023-09-27T03:40:14 Z abcvuitunggio Highway Tolls (IOI18_highway) C++17
51 / 100
 114 ms 10332 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][0]==-1)
            d[i][0]=1e9;
        if (d[i][1]==-1)
            d[i][1]=1e9;
        if (d[i][1]>d[i][0]+1)
            type[i]=1;
        if (d[i][0]>d[i][1]+1)
            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:70: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]
   70 |         for (int i=mid;i<a.size();i++)
      |                        ~^~~~~~~~~
highway.cpp:78: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]
   78 |         for (int i=mid;i<a.size();i++)
      |                        ~^~~~~~~~~
highway.cpp:85: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]
   85 |         for (int i=mid;i<b.size();i++)
      |                        ~^~~~~~~~~
highway.cpp:93: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]
   93 |         for (int i=mid;i<b.size();i++)
      |                        ~^~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3376 KB Output is correct
2 Correct 1 ms 3160 KB Output is correct
3 Correct 1 ms 3372 KB Output is correct
4 Correct 1 ms 3368 KB Output is correct
5 Correct 1 ms 3160 KB Output is correct
6 Correct 1 ms 3372 KB Output is correct
7 Correct 1 ms 3160 KB Output is correct
8 Correct 1 ms 3160 KB Output is correct
9 Correct 1 ms 3372 KB Output is correct
10 Correct 1 ms 3368 KB Output is correct
11 Correct 1 ms 3372 KB Output is correct
12 Correct 1 ms 3368 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3388 KB Output is correct
2 Correct 10 ms 4100 KB Output is correct
3 Correct 84 ms 9200 KB Output is correct
4 Correct 78 ms 9364 KB Output is correct
5 Correct 81 ms 9360 KB Output is correct
6 Correct 68 ms 8832 KB Output is correct
7 Correct 77 ms 8572 KB Output is correct
8 Correct 85 ms 9392 KB Output is correct
9 Correct 74 ms 8860 KB Output is correct
10 Correct 80 ms 8928 KB Output is correct
11 Correct 66 ms 8384 KB Output is correct
12 Correct 85 ms 9332 KB Output is correct
13 Correct 83 ms 9356 KB Output is correct
14 Correct 83 ms 9336 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 3988 KB Output is correct
2 Correct 14 ms 4544 KB Output is correct
3 Correct 19 ms 4136 KB Output is correct
4 Correct 61 ms 7888 KB Output is correct
5 Correct 52 ms 7696 KB Output is correct
6 Correct 48 ms 8568 KB Output is correct
7 Correct 54 ms 5396 KB Output is correct
8 Correct 57 ms 7976 KB Output is correct
9 Correct 53 ms 6264 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3388 KB Output is correct
2 Correct 10 ms 4068 KB Output is correct
3 Correct 60 ms 8184 KB Output is correct
4 Correct 86 ms 9348 KB Output is correct
5 Correct 61 ms 7968 KB Output is correct
6 Correct 61 ms 8204 KB Output is correct
7 Correct 75 ms 9060 KB Output is correct
8 Correct 61 ms 8432 KB Output is correct
9 Correct 87 ms 9332 KB Output is correct
10 Correct 74 ms 9444 KB Output is correct
11 Correct 83 ms 9588 KB Output is correct
12 Correct 87 ms 8916 KB Output is correct
13 Correct 80 ms 9036 KB Output is correct
14 Correct 66 ms 8492 KB Output is correct
15 Correct 62 ms 8208 KB Output is correct
16 Correct 59 ms 7232 KB Output is correct
17 Correct 90 ms 9360 KB Output is correct
18 Correct 84 ms 9464 KB Output is correct
19 Correct 59 ms 7800 KB Output is correct
20 Correct 68 ms 8232 KB Output is correct
21 Correct 62 ms 8056 KB Output is correct
22 Correct 53 ms 6836 KB Output is correct
23 Correct 76 ms 10292 KB Output is correct
24 Correct 73 ms 9784 KB Output is correct
25 Correct 79 ms 9388 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 4184 KB Output is correct
2 Correct 11 ms 4176 KB Output is correct
3 Correct 84 ms 9552 KB Output is correct
4 Correct 93 ms 9112 KB Output is correct
5 Correct 103 ms 10100 KB Output is correct
6 Correct 112 ms 10012 KB Output is correct
7 Correct 110 ms 10180 KB Output is correct
8 Correct 110 ms 9896 KB Output is correct
9 Incorrect 78 ms 5952 KB Output is incorrect: {s, t} is wrong.
10 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 4024 KB Output is correct
2 Correct 11 ms 4268 KB Output is correct
3 Correct 103 ms 9672 KB Output is correct
4 Correct 91 ms 9128 KB Output is correct
5 Correct 94 ms 9376 KB Output is correct
6 Correct 112 ms 10332 KB Output is correct
7 Correct 91 ms 9664 KB Output is correct
8 Correct 106 ms 9688 KB Output is correct
9 Correct 100 ms 9784 KB Output is correct
10 Correct 110 ms 9984 KB Output is correct
11 Correct 113 ms 9756 KB Output is correct
12 Correct 114 ms 9976 KB Output is correct
13 Incorrect 86 ms 6204 KB Output is incorrect: {s, t} is wrong.
14 Halted 0 ms 0 KB -