oj.uz

Submission #880644

# Submission time Handle Problem Language Result Execution time Memory
880644 2023-11-29T19:25:27 Z andrei_boaca Highway Tolls (IOI18_highway) C++17
18 / 100
 148 ms 13112 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)
            w[i]=1;
        else
            w[i]=0;
    }
    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]=1;
        else
            w[i]=0;
    }
    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)*AA+mij*BB)
        {
            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*AA)
            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 1 ms 4696 KB Output is correct
2 Correct 1 ms 4560 KB Output is correct
3 Correct 1 ms 4560 KB Output is correct
4 Correct 1 ms 4564 KB Output is correct
5 Correct 1 ms 4808 KB Output is correct
6 Correct 1 ms 4564 KB Output is correct
7 Correct 1 ms 4568 KB Output is correct
8 Correct 1 ms 4564 KB Output is correct
9 Correct 1 ms 4568 KB Output is correct
10 Correct 1 ms 4560 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 14 ms 5288 KB Output is correct
3 Correct 89 ms 11980 KB Output is correct
4 Correct 92 ms 11628 KB Output is correct
5 Correct 134 ms 12012 KB Output is correct
6 Correct 91 ms 11660 KB Output is correct
7 Correct 122 ms 12012 KB Output is correct
8 Correct 100 ms 11388 KB Output is correct
9 Correct 90 ms 11404 KB Output is correct
10 Correct 115 ms 11736 KB Output is correct
11 Correct 113 ms 11392 KB Output is correct
12 Correct 110 ms 11944 KB Output is correct
13 Correct 85 ms 11656 KB Output is correct
14 Correct 95 ms 11476 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 5332 KB Output is correct
2 Correct 25 ms 5740 KB Output is correct
3 Correct 24 ms 6752 KB Output is correct
4 Correct 72 ms 11372 KB Output is correct
5 Correct 72 ms 11160 KB Output is correct
6 Correct 77 ms 11152 KB Output is correct
7 Correct 91 ms 11152 KB Output is correct
8 Correct 62 ms 11412 KB Output is correct
9 Correct 84 ms 11160 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 15 ms 5452 KB Output is correct
3 Correct 63 ms 10032 KB Output is correct
4 Correct 108 ms 11432 KB Output is correct
5 Correct 109 ms 11528 KB Output is correct
6 Correct 110 ms 11624 KB Output is correct
7 Correct 95 ms 11392 KB Output is correct
8 Correct 78 ms 11448 KB Output is correct
9 Correct 138 ms 11484 KB Output is correct
10 Correct 97 ms 11644 KB Output is correct
11 Correct 108 ms 11956 KB Output is correct
12 Correct 139 ms 11468 KB Output is correct
13 Correct 134 ms 12212 KB Output is correct
14 Correct 143 ms 11488 KB Output is correct
15 Correct 68 ms 11392 KB Output is correct
16 Correct 67 ms 11300 KB Output is correct
17 Correct 108 ms 11964 KB Output is correct
18 Correct 119 ms 11648 KB Output is correct
19 Correct 79 ms 11620 KB Output is correct
20 Correct 141 ms 11628 KB Output is correct
21 Correct 100 ms 12920 KB Output is correct
22 Correct 84 ms 13112 KB Output is correct
23 Incorrect 148 ms 12712 KB Output isn't correct
24 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 5284 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 9 ms 5212 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -