oj.uz

Submission #880651

# Submission time Handle Problem Language Result Execution time Memory
880651 2023-11-29T19:34:56 Z andrei_boaca Highway Tolls (IOI18_highway) C++17
18 / 100
 160 ms 13124 KB 
#include "highway.h"
#include <bits/stdc++.h>
//#include "grader.cpp"
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
mt19937 rng(chrono::steady_clock().now().time_since_epoch().count());
int n,m,niv[100005],roots[5];
ll dist,AA,BB,d[3][100005];
vector<int> muchii[100005];
vector<pii> g;
vector<int> w;
ll memo[100005],calls;
void bfs(int ind)
{
    for(int i=0;i<n;i++)
        d[ind][i]=1e9;
    d[ind][roots[ind]]=0;
    queue<int> coada;
    coada.push(roots[ind]);
    while(!coada.empty())
    {
        int nod=coada.front();
        coada.pop();
        for(int i:muchii[nod])
            if(d[ind][i]>d[ind][nod]+1)
            {
                d[ind][i]=d[ind][nod]+1;
                coada.push(i);
            }
    }
}
bool good[100005],mark[100005];
ll firstsearch(ll ind,ll nivmax)
{
    for(int i=0;i<m;i++)
    {
        ll a=g[i].first;
        ll b=g[i].second;
        if(d[ind][a]<d[ind][b])
            swap(a,b);
        if(good[a]&&d[ind][a]<=nivmax&&d[ind][a]==d[ind][b]+1)
            w[i]=0;
        else
            w[i]=1;
    }
    return ask(w);
}
ll secondsearch(ll ind)
{
    for(int i=0;i<m;i++)
    {
        ll a=g[i].first;
        ll b=g[i].second;
        if(d[ind][a]<d[ind][b])
            swap(a,b);
        if(mark[a]&&d[ind][a]==d[ind][b]+1)
            w[i]=0;
        else
            w[i]=1;
    }
    return ask(w);
}
int plsfind(int ind)
{
    int u=roots[ind];
    ll nivmax=0;
    for(int i=0;i<n;i++)
    {
        good[i]=0;
        if(d[ind][i]<d[3-ind][i])
        {
            nivmax=max(nivmax,d[ind][i]);
            good[i]=1;
        }
    }
    int myniv=0;
    int st=0;
    int dr=nivmax;
    while(st<=dr)
    {
        int mij=(st+dr)/2;
        ll val=firstsearch(ind,mij);
        if(mij<=dist&&val==(dist-mij)*BB+mij*AA)
        {
            myniv=mij;
            st=mij+1;
        }
        else
            dr=mij-1;
    }
    vector<int> cand;
    for(int i=0;i<n;i++)
        if(good[i]&&d[ind][i]==myniv)
            cand.push_back(i);
    while(true)
    {
        if(cand.size()==1)
            return cand[0];
        vector<int> x;
        vector<int> y;
        int lg=cand.size();
        for(int i=0;i<cand.size();i++)
        {
            if(i<lg/2)
                x.push_back(cand[i]);
            else
                y.push_back(cand[i]);
        }
        for(int i=0;i<n;i++)
            mark[i]=0;
        for(int i:x)
            mark[i]=1;
        ll val=secondsearch(ind);
        if(val<dist*BB)
            cand=x;
        else
            cand=y;
    }
}
void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B)
{
    AA=A;
    BB=B;
    n=N;
    m=U.size();
    for(int i=0;i<m;i++)
    {
        int a=U[i],b=V[i];
        g.push_back({a,b});
        muchii[a].push_back(b);
        muchii[b].push_back(a);
    }
    w.resize(m);
    dist=ask(w)/A;
    ll st=0;
    ll dr=m-1;
    while(st<=dr)
    {
        ll mij=(st+dr)/2;
        for(int i=0;i<m;i++)
        {
            if(i<=mij)
                w[i]=1;
            else
                w[i]=0;
        }
        ll val=ask(w);
        if(val>dist*A)
        {
            roots[1]=g[mij].first;
            roots[2]=g[mij].second;
            dr=mij-1;
        }
        else
            st=mij+1;
    }
    bfs(1);
    bfs(2);
    int S=plsfind(1);
    int T=plsfind(2);
    answer(S,T);
}

Compilation message

highway.cpp: In function 'int plsfind(int)':
highway.cpp:103:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  103 |         for(int i=0;i<cand.size();i++)
      |                     ~^~~~~~~~~~~~
highway.cpp:66:9: warning: unused variable 'u' [-Wunused-variable]
   66 |     int u=roots[ind];
      |         ^

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4616 KB Output is correct
2 Correct 11 ms 5364 KB Output is correct
3 Correct 106 ms 11976 KB Output is correct
4 Correct 111 ms 12092 KB Output is correct
5 Correct 100 ms 11976 KB Output is correct
6 Correct 89 ms 11640 KB Output is correct
7 Correct 88 ms 11980 KB Output is correct
8 Correct 101 ms 11632 KB Output is correct
9 Correct 89 ms 11624 KB Output is correct
10 Correct 96 ms 11972 KB Output is correct
11 Correct 160 ms 12096 KB Output is correct
12 Correct 139 ms 11600 KB Output is correct
13 Correct 117 ms 12088 KB Output is correct
14 Correct 129 ms 12180 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5256 KB Output is correct
2 Correct 26 ms 5924 KB Output is correct
3 Correct 42 ms 6660 KB Output is correct
4 Correct 73 ms 11152 KB Output is correct
5 Correct 76 ms 11400 KB Output is correct
6 Correct 110 ms 11152 KB Output is correct
7 Correct 128 ms 11156 KB Output is correct
8 Correct 91 ms 11392 KB Output is correct
9 Correct 108 ms 11368 KB Output is correct

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4616 KB Output is correct
2 Correct 16 ms 5292 KB Output is correct
3 Correct 69 ms 10100 KB Output is correct
4 Correct 100 ms 11664 KB Output is correct
5 Correct 94 ms 11616 KB Output is correct
6 Correct 82 ms 11608 KB Output is correct
7 Correct 115 ms 11628 KB Output is correct
8 Correct 88 ms 11616 KB Output is correct
9 Correct 109 ms 11956 KB Output is correct
10 Correct 106 ms 11972 KB Output is correct
11 Correct 116 ms 11624 KB Output is correct
12 Correct 122 ms 11624 KB Output is correct
13 Correct 150 ms 11708 KB Output is correct
14 Correct 126 ms 11408 KB Output is correct
15 Correct 96 ms 11544 KB Output is correct
16 Correct 128 ms 11760 KB Output is correct
17 Correct 114 ms 11476 KB Output is correct
18 Correct 117 ms 12100 KB Output is correct
19 Correct 82 ms 11864 KB Output is correct
20 Correct 105 ms 11492 KB Output is correct
21 Correct 82 ms 12884 KB Output is correct
22 Correct 109 ms 12888 KB Output is correct
23 Incorrect 132 ms 13124 KB Output isn't correct
24 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 5388 KB Output is correct
2 Incorrect 16 ms 5336 KB Output is incorrect: {s, t} is wrong.
3 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

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