oj.uz

Submission #881456

# Submission time Handle Problem Language Result Execution time Memory
881456 2023-12-01T09:05:08 Z andrei_boaca Highway Tolls (IOI18_highway) C++17
18 / 100
 122 ms 14384 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;
        if(d[2][i]<d[1][i])
            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 2 ms 6612 KB Output is correct
2 Correct 1 ms 6612 KB Output is correct
3 Correct 1 ms 6616 KB Output is correct
4 Correct 2 ms 6616 KB Output is correct
5 Correct 1 ms 6612 KB Output is correct
6 Correct 2 ms 6620 KB Output is correct
7 Correct 1 ms 6620 KB Output is correct
8 Correct 1 ms 6616 KB Output is correct
9 Correct 2 ms 6612 KB Output is correct
10 Correct 1 ms 6616 KB Output is correct
11 Correct 1 ms 6616 KB Output is correct
12 Correct 1 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 14 ms 7356 KB Output is correct
3 Correct 96 ms 12984 KB Output is correct
4 Correct 99 ms 12976 KB Output is correct
5 Correct 95 ms 12976 KB Output is correct
6 Correct 89 ms 12892 KB Output is correct
7 Correct 96 ms 12756 KB Output is correct
8 Correct 119 ms 13092 KB Output is correct
9 Correct 79 ms 13008 KB Output is correct
10 Correct 88 ms 12960 KB Output is correct
11 Correct 91 ms 12180 KB Output is correct
12 Correct 94 ms 12504 KB Output is correct
13 Correct 86 ms 12036 KB Output is correct
14 Correct 104 ms 12172 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 7216 KB Output is correct
2 Correct 18 ms 7800 KB Output is correct
3 Correct 23 ms 8632 KB Output is correct
4 Correct 72 ms 12196 KB Output is correct
5 Correct 70 ms 12076 KB Output is correct
6 Correct 71 ms 12368 KB Output is correct
7 Correct 98 ms 11948 KB Output is correct
8 Correct 73 ms 11972 KB Output is correct
9 Correct 66 ms 11964 KB Output is correct

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6672 KB Output is correct
2 Correct 12 ms 7296 KB Output is correct
3 Correct 62 ms 11440 KB Output is correct
4 Correct 95 ms 12920 KB Output is correct
5 Correct 84 ms 12624 KB Output is correct
6 Correct 101 ms 12616 KB Output is correct
7 Correct 88 ms 12644 KB Output is correct
8 Correct 75 ms 12624 KB Output is correct
9 Correct 78 ms 12876 KB Output is correct
10 Correct 106 ms 12752 KB Output is correct
11 Correct 90 ms 12268 KB Output is correct
12 Correct 122 ms 12260 KB Output is correct
13 Correct 94 ms 12584 KB Output is correct
14 Correct 103 ms 12268 KB Output is correct
15 Correct 114 ms 12716 KB Output is correct
16 Correct 92 ms 12552 KB Output is correct
17 Correct 87 ms 12276 KB Output is correct
18 Correct 105 ms 12412 KB Output is correct
19 Correct 94 ms 13100 KB Output is correct
20 Correct 78 ms 12036 KB Output is correct
21 Correct 103 ms 14384 KB Output is correct
22 Correct 89 ms 13908 KB Output is correct
23 Incorrect 106 ms 13772 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 7328 KB Output is correct
2 Incorrect 11 ms 7440 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 14 ms 7324 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -