oj.uz

Submission #767117

# Submission time Handle Problem Language Result Execution time Memory
767117 2023-06-26T11:51:34 Z DJeniUp Highway Tolls (IOI18_highway) C++17
100 / 100
 288 ms 16264 KB 
#include "highway.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<ll,ll>pairll;

#define pb push_back
#define fr first
#define sc second
#define INF 10000000000000007

ll n,m,k,d[90007],fl[90007],d1[90007];

vector<pairll>v[90007],g;

priority_queue<pairll, vector<pairll>, greater<pairll> >q;

vector<int>f;

ll S(ll x){
    for(int i=0;i<m;i++){
        f[i]=0;
    }
    for(int i=0;i<=x;i++){
        for(int j=0;j<v[g[i].sc].size();j++){
            f[v[g[i].sc][j].fr]=1;
        }
    }
    ll k1=ask(f);
    if(k1!=k)return 1;
    return 0;
}

bool mcp(pairll g1, pairll g2){
    return g1.fr>g2.fr;
}

ll D(ll x){
    g.clear();
    for(int i=0;i<n;i++){
        d[i]=INF;
        d1[i]=INF;
    }
    d[x]=0;
    q.push({0,x});
    while(q.size()>0){
        ll m1=q.top().fr;
        ll m2=q.top().sc;
        q.pop();
        for(int i=0;i<v[m2].size();i++){
            if(d[v[m2][i].sc]>m1+1){
                d[v[m2][i].sc]=m1+1;
                q.push({m1+1,v[m2][i].sc});
            }
        }
    }

    d1[x]=0;
    q.push({0,x});
    while(q.size()>0){
        ll m1=q.top().fr;
        ll m2=q.top().sc;
        q.pop();
        if(fl[m2]==0){
            for(int i=0;i<v[m2].size();i++){
                if(d1[v[m2][i].sc]>m1+1){
                    d1[v[m2][i].sc]=m1+1;
                    q.push({m1+1,v[m2][i].sc});
                }
            }
        }
    }
    for(int i=0;i<n;i++){
        if(fl[i]!=1 && d[i]==d1[i]){
            g.pb({d[i],i});
            //cout<<i<<endl;
        }
    }
    sort(g.begin(),g.end(),mcp);

    ll l=0;
    ll r=g.size()-1;
    while(l<r){
        ll m1=(l+r)/2;
        if(S(m1)==0)l=m1+1;
        else r=m1;
    }
    for(int i=0;i<l;i++){
        fl[g[i].sc]=1;
    }
    return g[l].sc;
}

void find_pair(int _N, vector<int> U, vector<int> V, int A, int B) {
    n=_N;
    m=U.size();
    for(int i=0;i<m;i++){
        v[U[i]].pb({i,V[i]});
        v[V[i]].pb({i,U[i]});
        f.pb(0);
    }
    for(int i=0;i<n;i++)g.pb({0,i});
    k=ask(f);
    ll l=0;
    ll r=n-1;
    while(l<r){
        ll m1=(l+r)/2;
        if(S(m1)==0)l=m1+1;
        else r=m1;
    }
    for(int i=0;i<l;i++){
        fl[g[i].sc]=1;
    }
    ll s=D(l);
    ll t=D(s);
    //cout<<s<<" "<<t<<endl;
    answer(s,t);
    return ;
}

Compilation message

highway.cpp: In function 'll S(ll)':
highway.cpp:26:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |         for(int j=0;j<v[g[i].sc].size();j++){
      |                     ~^~~~~~~~~~~~~~~~~~
highway.cpp: In function 'll D(ll)':
highway.cpp:51:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |         for(int i=0;i<v[m2].size();i++){
      |                     ~^~~~~~~~~~~~~
highway.cpp:66:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |             for(int i=0;i<v[m2].size();i++){
      |                         ~^~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2384 KB Output is correct
2 Correct 2 ms 2384 KB Output is correct
3 Correct 1 ms 2424 KB Output is correct
4 Correct 2 ms 2384 KB Output is correct
5 Correct 1 ms 2384 KB Output is correct
6 Correct 2 ms 2384 KB Output is correct
7 Correct 1 ms 2428 KB Output is correct
8 Correct 1 ms 2384 KB Output is correct
9 Correct 1 ms 2384 KB Output is correct
10 Correct 1 ms 2384 KB Output is correct
11 Correct 2 ms 2384 KB Output is correct
12 Correct 2 ms 2436 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2512 KB Output is correct
2 Correct 14 ms 3564 KB Output is correct
3 Correct 225 ms 12756 KB Output is correct
4 Correct 194 ms 12772 KB Output is correct
5 Correct 230 ms 12780 KB Output is correct
6 Correct 194 ms 12836 KB Output is correct
7 Correct 176 ms 12776 KB Output is correct
8 Correct 198 ms 12784 KB Output is correct
9 Correct 211 ms 12764 KB Output is correct
10 Correct 195 ms 12748 KB Output is correct
11 Correct 288 ms 12528 KB Output is correct
12 Correct 225 ms 12536 KB Output is correct
13 Correct 187 ms 12544 KB Output is correct
14 Correct 271 ms 12524 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 3524 KB Output is correct
2 Correct 24 ms 4540 KB Output is correct
3 Correct 21 ms 5632 KB Output is correct
4 Correct 117 ms 11816 KB Output is correct
5 Correct 108 ms 11924 KB Output is correct
6 Correct 106 ms 11496 KB Output is correct
7 Correct 91 ms 12056 KB Output is correct
8 Correct 91 ms 11800 KB Output is correct
9 Correct 104 ms 12028 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2512 KB Output is correct
2 Correct 14 ms 3660 KB Output is correct
3 Correct 122 ms 10556 KB Output is correct
4 Correct 178 ms 12596 KB Output is correct
5 Correct 165 ms 12720 KB Output is correct
6 Correct 145 ms 12616 KB Output is correct
7 Correct 130 ms 12756 KB Output is correct
8 Correct 124 ms 12632 KB Output is correct
9 Correct 187 ms 12748 KB Output is correct
10 Correct 195 ms 12772 KB Output is correct
11 Correct 144 ms 12640 KB Output is correct
12 Correct 142 ms 12532 KB Output is correct
13 Correct 154 ms 12524 KB Output is correct
14 Correct 174 ms 12528 KB Output is correct
15 Correct 171 ms 12752 KB Output is correct
16 Correct 141 ms 12672 KB Output is correct
17 Correct 153 ms 12536 KB Output is correct
18 Correct 138 ms 12508 KB Output is correct
19 Correct 132 ms 12300 KB Output is correct
20 Correct 100 ms 12416 KB Output is correct
21 Correct 160 ms 14392 KB Output is correct
22 Correct 136 ms 14684 KB Output is correct
23 Correct 164 ms 13424 KB Output is correct
24 Correct 185 ms 13008 KB Output is correct
25 Correct 160 ms 11940 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 3668 KB Output is correct
2 Correct 20 ms 3732 KB Output is correct
3 Correct 139 ms 13832 KB Output is correct
4 Correct 182 ms 14584 KB Output is correct
5 Correct 225 ms 16152 KB Output is correct
6 Correct 189 ms 16164 KB Output is correct
7 Correct 223 ms 16168 KB Output is correct
8 Correct 221 ms 16152 KB Output is correct
9 Correct 163 ms 11652 KB Output is correct
10 Correct 135 ms 12824 KB Output is correct
11 Correct 122 ms 13976 KB Output is correct
12 Correct 181 ms 15352 KB Output is correct
13 Correct 238 ms 15780 KB Output is correct
14 Correct 217 ms 16116 KB Output is correct
15 Correct 237 ms 16120 KB Output is correct
16 Correct 147 ms 14108 KB Output is correct
17 Correct 149 ms 14416 KB Output is correct
18 Correct 121 ms 15388 KB Output is correct
19 Correct 168 ms 14672 KB Output is correct
20 Correct 114 ms 14616 KB Output is correct
21 Correct 233 ms 15580 KB Output is correct

Subtask #6
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 3664 KB Output is correct
2 Correct 18 ms 3692 KB Output is correct
3 Correct 187 ms 13880 KB Output is correct
4 Correct 223 ms 14228 KB Output is correct
5 Correct 170 ms 14632 KB Output is correct
6 Correct 250 ms 16264 KB Output is correct
7 Correct 152 ms 13912 KB Output is correct
8 Correct 198 ms 14240 KB Output is correct
9 Correct 224 ms 14612 KB Output is correct
10 Correct 248 ms 16060 KB Output is correct
11 Correct 219 ms 16156 KB Output is correct
12 Correct 221 ms 16164 KB Output is correct
13 Correct 200 ms 13840 KB Output is correct
14 Correct 145 ms 12804 KB Output is correct
15 Correct 170 ms 13880 KB Output is correct
16 Correct 191 ms 12700 KB Output is correct
17 Correct 136 ms 13928 KB Output is correct
18 Correct 113 ms 12692 KB Output is correct
19 Correct 255 ms 15360 KB Output is correct
20 Correct 183 ms 15712 KB Output is correct
21 Correct 255 ms 16060 KB Output is correct
22 Correct 200 ms 16196 KB Output is correct
23 Correct 220 ms 16024 KB Output is correct
24 Correct 235 ms 16096 KB Output is correct
25 Correct 203 ms 16120 KB Output is correct
26 Correct 206 ms 16136 KB Output is correct
27 Correct 169 ms 14800 KB Output is correct
28 Correct 146 ms 14464 KB Output is correct
29 Correct 152 ms 15116 KB Output is correct
30 Correct 138 ms 14740 KB Output is correct
31 Correct 177 ms 14508 KB Output is correct
32 Correct 151 ms 14452 KB Output is correct
33 Correct 168 ms 15084 KB Output is correct
34 Correct 169 ms 14564 KB Output is correct
35 Correct 166 ms 14508 KB Output is correct
36 Correct 163 ms 14484 KB Output is correct
37 Correct 153 ms 15016 KB Output is correct
38 Correct 172 ms 14984 KB Output is correct
39 Correct 187 ms 15484 KB Output is correct
40 Correct 200 ms 15472 KB Output is correct
41 Correct 192 ms 15472 KB Output is correct
42 Correct 154 ms 15468 KB Output is correct