oj.uz

Submission #854353

# Submission time Handle Problem Language Result Execution time Memory
854353 2023-09-27T03:27:33 Z abcvuitunggio Highway Tolls (IOI18_highway) C++17
51 / 100
 122 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][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 3368 KB Output is correct
2 Correct 1 ms 3364 KB Output is correct
3 Correct 1 ms 3376 KB Output is correct
4 Correct 1 ms 3372 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 3168 KB Output is correct
9 Correct 1 ms 3372 KB Output is correct
10 Correct 2 ms 3372 KB Output is correct
11 Correct 1 ms 3376 KB Output is correct
12 Correct 1 ms 3372 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3384 KB Output is correct
2 Correct 9 ms 4100 KB Output is correct
3 Correct 89 ms 9344 KB Output is correct
4 Correct 77 ms 9352 KB Output is correct
5 Correct 75 ms 9560 KB Output is correct
6 Correct 72 ms 8828 KB Output is correct
7 Correct 64 ms 8576 KB Output is correct
8 Correct 80 ms 9400 KB Output is correct
9 Correct 70 ms 8856 KB Output is correct
10 Correct 80 ms 9160 KB Output is correct
11 Correct 65 ms 8392 KB Output is correct
12 Correct 85 ms 9312 KB Output is correct
13 Correct 82 ms 9336 KB Output is correct
14 Correct 94 ms 9332 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 3988 KB Output is correct
2 Correct 12 ms 4536 KB Output is correct
3 Correct 16 ms 4140 KB Output is correct
4 Correct 59 ms 7892 KB Output is correct
5 Correct 59 ms 7704 KB Output is correct
6 Correct 61 ms 8564 KB Output is correct
7 Correct 54 ms 5388 KB Output is correct
8 Correct 66 ms 7968 KB Output is correct
9 Correct 57 ms 6248 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 4160 KB Output is correct
3 Correct 64 ms 8204 KB Output is correct
4 Correct 76 ms 9344 KB Output is correct
5 Correct 56 ms 8212 KB Output is correct
6 Correct 68 ms 8184 KB Output is correct
7 Correct 76 ms 8604 KB Output is correct
8 Correct 66 ms 8432 KB Output is correct
9 Correct 89 ms 9580 KB Output is correct
10 Correct 79 ms 9000 KB Output is correct
11 Correct 83 ms 9356 KB Output is correct
12 Correct 92 ms 9140 KB Output is correct
13 Correct 77 ms 9040 KB Output is correct
14 Correct 71 ms 8488 KB Output is correct
15 Correct 69 ms 8528 KB Output is correct
16 Correct 57 ms 7248 KB Output is correct
17 Correct 85 ms 9332 KB Output is correct
18 Correct 81 ms 9356 KB Output is correct
19 Correct 56 ms 7816 KB Output is correct
20 Correct 60 ms 8252 KB Output is correct
21 Correct 70 ms 8060 KB Output is correct
22 Correct 57 ms 6840 KB Output is correct
23 Correct 73 ms 9572 KB Output is correct
24 Correct 72 ms 9756 KB Output is correct
25 Correct 78 ms 9368 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 4016 KB Output is correct
3 Correct 90 ms 9536 KB Output is correct
4 Correct 96 ms 9292 KB Output is correct
5 Correct 109 ms 9648 KB Output is correct
6 Correct 122 ms 10228 KB Output is correct
7 Correct 101 ms 10144 KB Output is correct
8 Correct 109 ms 10144 KB Output is correct
9 Incorrect 76 ms 5940 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 4016 KB Output is correct
2 Correct 12 ms 4216 KB Output is correct
3 Correct 89 ms 9880 KB Output is correct
4 Correct 107 ms 9112 KB Output is correct
5 Correct 93 ms 9592 KB Output is correct
6 Correct 114 ms 10120 KB Output is correct
7 Correct 88 ms 9656 KB Output is correct
8 Correct 102 ms 9976 KB Output is correct
9 Correct 92 ms 9372 KB Output is correct
10 Correct 107 ms 9788 KB Output is correct
11 Correct 110 ms 9976 KB Output is correct
12 Correct 110 ms 9604 KB Output is correct
13 Incorrect 76 ms 5984 KB Output is incorrect: {s, t} is wrong.
14 Halted 0 ms 0 KB -