oj.uz

Submission #881458

# Submission time Handle Problem Language Result Execution time Memory
881458 2023-12-01T09:06:13 Z andrei_boaca Highway Tolls (IOI18_highway) C++17
18 / 100
 149 ms 14260 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];
int where[100005];
vector<pii> muchii[100005];
vector<pii> g;
vector<int> w;
ll memo[100005],calls;
bool inarb[300005],inx[300005];
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(auto i:muchii[nod])
            if(d[ind][i.first]>d[ind][nod]+1)
            {
                d[ind][i.first]=d[ind][nod]+1;
                coada.push(i.first);
            }
    }
}
ll buildniv(ll nivmax,ll ind)
{
    for(int i=0;i<m;i++)
    {
        if(inarb[i]==0)
        {
            w[i]=1;
            continue;
        }
        int a=g[i].first,b=g[i].second;
        if(max(d[ind][a],d[ind][b])<=nivmax)
            w[i]=0;
        else
            w[i]=1;
    }
    return ask(w);
}
ll buildx(int ind)
{
    for(int i=0;i<m;i++)
    {
        if(inarb[i]==0)
        {
            w[i]=1;
            continue;
        }
        int a=g[i].first,b=g[i].second;
        if(d[ind][a]<d[ind][b])
            swap(a,b);
        if(inx[a])
            w[i]=0;
        else
            w[i]=1;
    }
    return ask(w);
}
int plsfind(int ind)
{
    for(int i=0;i<m;i++)
        inarb[i]=0;
    for(int i=0;i<n;i++)
        d[ind][i]=1e9;
    ll nivmax=0;
    d[ind][roots[ind]]=0;
    queue<int> coada;
    coada.push(roots[ind]);
    while(!coada.empty())
    {
        int nod=coada.front();
        nivmax=max(nivmax,d[ind][nod]);
        coada.pop();
        for(auto i:muchii[nod])
            if(where[i.first]==ind&&d[ind][i.first]>d[ind][nod]+1)
            {
                d[ind][i.first]=d[ind][nod]+1;
                inarb[i.second]=1;
                coada.push(i.first);
            }
    }
    int myniv=0;
    int st=0;
    int dr=min(nivmax,dist);
    while(st<=dr)
    {
        int mij=(st+dr)/2;
        ll val=buildniv(mij,ind);
        if(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(d[ind][i]==myniv&&where[i]==ind)
            cand.push_back(i);
    while(true)
    {
        if(cand.size()==1)
            return cand[0];
        int lg=cand.size();
        vector<int> x,y;
        for(int i=0;i<n;i++)
            inx[i]=0;
        for(int i=0;i<cand.size();i++)
        {
            if(i<lg/2)
            {
                x.push_back(cand[i]);
                inx[cand[i]]=1;
            }
            else
                y.push_back(cand[i]);
        }
        bool ok=0;
        if(ind==2)
            ok=1;
        ll val=buildx(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,i});
        muchii[b].push_back({a,i});
    }
    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);
    for(int i=0;i<n;i++)
    {
        if(d[1][i]<d[2][i])
            where[i]=1;
        else
            where[i]=2;
    }
    int S=plsfind(1);
    int T=plsfind(2);
    answer(S,T);
}

Compilation message

highway.cpp: In function 'int plsfind(int)':
highway.cpp:121:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  121 |         for(int i=0;i<cand.size();i++)
      |                     ~^~~~~~~~~~~~
highway.cpp:131:14: warning: variable 'ok' set but not used [-Wunused-but-set-variable]
  131 |         bool ok=0;
      |              ^~

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6676 KB Output is correct
2 Correct 9 ms 7284 KB Output is correct
3 Correct 101 ms 12768 KB Output is correct
4 Correct 86 ms 12976 KB Output is correct
5 Correct 95 ms 12988 KB Output is correct
6 Correct 90 ms 12888 KB Output is correct
7 Correct 101 ms 12748 KB Output is correct
8 Correct 118 ms 12632 KB Output is correct
9 Correct 118 ms 12640 KB Output is correct
10 Correct 104 ms 12984 KB Output is correct
11 Correct 75 ms 12268 KB Output is correct
12 Correct 100 ms 12744 KB Output is correct
13 Correct 105 ms 12164 KB Output is correct
14 Correct 129 ms 12272 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7284 KB Output is correct
2 Correct 28 ms 7804 KB Output is correct
3 Correct 36 ms 8376 KB Output is correct
4 Correct 69 ms 11948 KB Output is correct
5 Correct 91 ms 11960 KB Output is correct
6 Correct 86 ms 12116 KB Output is correct
7 Correct 98 ms 11944 KB Output is correct
8 Correct 90 ms 12132 KB Output is correct
9 Correct 68 ms 11952 KB Output is correct

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6676 KB Output is correct
2 Correct 16 ms 7364 KB Output is correct
3 Correct 75 ms 11448 KB Output is correct
4 Correct 114 ms 12912 KB Output is correct
5 Correct 89 ms 12620 KB Output is correct
6 Correct 84 ms 13032 KB Output is correct
7 Correct 89 ms 12632 KB Output is correct
8 Correct 76 ms 12636 KB Output is correct
9 Correct 95 ms 12960 KB Output is correct
10 Correct 91 ms 12988 KB Output is correct
11 Correct 122 ms 12268 KB Output is correct
12 Correct 149 ms 12648 KB Output is correct
13 Correct 98 ms 13212 KB Output is correct
14 Correct 118 ms 12180 KB Output is correct
15 Correct 74 ms 12644 KB Output is correct
16 Correct 79 ms 12560 KB Output is correct
17 Correct 93 ms 12504 KB Output is correct
18 Correct 112 ms 12744 KB Output is correct
19 Correct 72 ms 12732 KB Output is correct
20 Correct 93 ms 12056 KB Output is correct
21 Correct 79 ms 14156 KB Output is correct
22 Correct 81 ms 14144 KB Output is correct
23 Incorrect 122 ms 14260 KB Output isn't correct
24 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 7404 KB Output is correct
2 Incorrect 11 ms 7620 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 12 ms 7464 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -