oj.uz

Submission #934897

# Submission time Handle Problem Language Result Execution time Memory
934897 2024-02-28T06:34:59 Z sleepntsheep Highway Tolls (IOI18_highway) C++17
51 / 100
 143 ms 10600 KB 
#include "highway.h"
#include<bits/stdc++.h>
using namespace std;

int ban[130000],n,m,a,b;std::vector<int>u,v;std::vector<std::pair<int,int>>g[90001];

int sub12(int src)
{
    vector<int>d(n,1e9),e(n,-1);
    queue<pair<int,int>>q; q.emplace(d[src]=0,src);
    while(q.size()){auto[c,u]=q.front();q.pop();for(auto[v,i]:g[u])if(!ban[i]&&d[v]>c+1)q.emplace(d[v]=c+1,v),e[v]=i;}

    long long need; {vector<int>qq(m);for(int i=0;i<n;++i)if(~e[i])qq[e[i]]=1;need=ask(qq);}

    vector<int>c;
    for(int i=0;i<n;++i)if(d[i]<1e9)c.push_back(i);
    sort(c.begin(),c.end(),[&d](int i,int v){return d[i]<d[v];});

    int z=0,l=0,r=c.size()-1;
    while(l<=r){
        int y=(l+r)/2;
        vector<int>qq(m,0);
        for(int i=1;i<=y;++i)if(~e[c[i]])qq[e[c[i]]]=1;
        if (ask(qq)==need)z=c[y],r=y-1;
        else l=y+1;
    }
    return z;
}

void sub1234(){
    long long need; {vector<int>qq(m,1); need=ask(qq);}
    auto dt = need / b;
    long long light = dt * a;

    int e1,l=0,r=m-1;
    while(l<=r) {
        int y=(l+r)/2;
        vector<int>qq(m);
        for(int i=0;i<=y;++i)qq[i]=1;
        if(ask(qq)>light)r=y-1,e1=y;
        else l=y+1;
    }

    int p=u[e1],q=v[e1];
    ban[e1]=1;
    int s=sub12(p);
    int t=sub12(q);

    answer(s,t);
}

void find_pair(int n_, std::vector<int> u_, std::vector<int> v_, int A_, int B_) {
    n=n_,u=u_,v=v_,a=A_,b=B_;m=u.size();
    for(int i=0;i<m;++i)g[u[i]].push_back({v[i],i}),g[v[i]].push_back({u[i],i});

    sub1234();

}

Compilation message

highway.cpp: In function 'void sub1234()':
highway.cpp:44:15: warning: 'e1' may be used uninitialized in this function [-Wmaybe-uninitialized]
   44 |     int p=u[e1],q=v[e1];
      |               ^

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2916 KB Output is correct
2 Correct 9 ms 3468 KB Output is correct
3 Correct 108 ms 10012 KB Output is correct
4 Correct 87 ms 10172 KB Output is correct
5 Correct 88 ms 10236 KB Output is correct
6 Correct 90 ms 9780 KB Output is correct
7 Correct 96 ms 10232 KB Output is correct
8 Correct 83 ms 9784 KB Output is correct
9 Correct 91 ms 10256 KB Output is correct
10 Correct 90 ms 10232 KB Output is correct
11 Correct 94 ms 9120 KB Output is correct
12 Correct 143 ms 9092 KB Output is correct
13 Correct 94 ms 9148 KB Output is correct
14 Correct 89 ms 9408 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 3352 KB Output is correct
2 Correct 16 ms 4224 KB Output is correct
3 Correct 22 ms 4920 KB Output is correct
4 Correct 115 ms 9140 KB Output is correct
5 Correct 94 ms 9420 KB Output is correct
6 Correct 74 ms 9108 KB Output is correct
7 Correct 115 ms 9164 KB Output is correct
8 Correct 72 ms 9164 KB Output is correct
9 Correct 101 ms 9076 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2732 KB Output is correct
2 Correct 10 ms 3460 KB Output is correct
3 Correct 68 ms 8360 KB Output is correct
4 Correct 94 ms 9772 KB Output is correct
5 Correct 102 ms 9808 KB Output is correct
6 Correct 94 ms 9756 KB Output is correct
7 Correct 86 ms 10000 KB Output is correct
8 Correct 111 ms 9776 KB Output is correct
9 Correct 88 ms 9960 KB Output is correct
10 Correct 90 ms 9992 KB Output is correct
11 Correct 119 ms 9612 KB Output is correct
12 Correct 101 ms 10072 KB Output is correct
13 Correct 125 ms 9132 KB Output is correct
14 Correct 90 ms 9372 KB Output is correct
15 Correct 77 ms 10020 KB Output is correct
16 Correct 91 ms 9780 KB Output is correct
17 Correct 93 ms 9136 KB Output is correct
18 Correct 100 ms 9176 KB Output is correct
19 Correct 77 ms 9784 KB Output is correct
20 Correct 81 ms 9364 KB Output is correct
21 Correct 68 ms 10600 KB Output is correct
22 Correct 70 ms 10104 KB Output is correct
23 Correct 96 ms 10012 KB Output is correct
24 Correct 94 ms 10156 KB Output is correct
25 Correct 93 ms 9712 KB Output is correct

Subtask #5
0 / 18.0

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

Subtask #6
0 / 31.0

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