oj.uz

Submission #880645

# Submission time Handle Problem Language Result Execution time Memory
880645 2023-11-29T19:27:29 Z andrei_boaca Highway Tolls (IOI18_highway) C++17
18 / 100
 155 ms 13128 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]=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 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 4568 KB Output is correct
5 Correct 1 ms 4560 KB Output is correct
6 Correct 1 ms 4564 KB Output is correct
7 Correct 1 ms 4560 KB Output is correct
8 Correct 1 ms 4564 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 4568 KB Output is correct
12 Correct 1 ms 4560 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4612 KB Output is correct
2 Correct 16 ms 5364 KB Output is correct
3 Correct 131 ms 11496 KB Output is correct
4 Correct 109 ms 11740 KB Output is correct
5 Correct 113 ms 11736 KB Output is correct
6 Correct 84 ms 11440 KB Output is correct
7 Correct 100 ms 11744 KB Output is correct
8 Correct 96 ms 11400 KB Output is correct
9 Correct 138 ms 11420 KB Output is correct
10 Correct 110 ms 11756 KB Output is correct
11 Correct 110 ms 11412 KB Output is correct
12 Correct 155 ms 11944 KB Output is correct
13 Correct 141 ms 11392 KB Output is correct
14 Correct 111 ms 11960 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 5328 KB Output is correct
2 Correct 16 ms 5744 KB Output is correct
3 Correct 28 ms 6824 KB Output is correct
4 Correct 97 ms 11156 KB Output is correct
5 Correct 65 ms 11180 KB Output is correct
6 Correct 76 ms 11400 KB Output is correct
7 Correct 70 ms 11580 KB Output is correct
8 Correct 90 ms 11372 KB Output is correct
9 Correct 112 ms 11404 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 12 ms 5292 KB Output is correct
3 Correct 59 ms 9860 KB Output is correct
4 Correct 127 ms 11436 KB Output is correct
5 Correct 135 ms 11556 KB Output is correct
6 Correct 86 ms 11400 KB Output is correct
7 Correct 89 ms 11400 KB Output is correct
8 Correct 80 ms 11400 KB Output is correct
9 Correct 100 ms 11752 KB Output is correct
10 Correct 124 ms 11788 KB Output is correct
11 Correct 104 ms 11512 KB Output is correct
12 Correct 138 ms 11940 KB Output is correct
13 Correct 141 ms 11712 KB Output is correct
14 Correct 122 ms 11720 KB Output is correct
15 Correct 114 ms 11388 KB Output is correct
16 Correct 67 ms 11504 KB Output is correct
17 Correct 129 ms 11496 KB Output is correct
18 Correct 116 ms 11496 KB Output is correct
19 Correct 77 ms 11396 KB Output is correct
20 Correct 95 ms 11480 KB Output is correct
21 Correct 123 ms 13128 KB Output is correct
22 Correct 83 ms 12652 KB Output is correct
23 Incorrect 144 ms 12196 KB Output isn't correct
24 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

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