oj.uz

Submission #880642

# Submission time Handle Problem Language Result Execution time Memory
880642 2023-11-29T19:23:49 Z andrei_boaca Highway Tolls (IOI18_highway) C++17
11 / 100
 125 ms 21676 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],par[100005],topar[100005],dp[21][100005],in[100005],out[100005],timp,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;
        bool ok=0;
        if(ind==2)
            ok=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<n;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:114:14: warning: variable 'ok' set but not used [-Wunused-but-set-variable]
  114 |         bool ok=0;
      |              ^~
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 6612 KB Output is correct
2 Correct 1 ms 6612 KB Output is correct
3 Correct 1 ms 6620 KB Output is correct
4 Correct 1 ms 6616 KB Output is correct
5 Correct 1 ms 6616 KB Output is correct
6 Correct 1 ms 6620 KB Output is correct
7 Correct 1 ms 6612 KB Output is correct
8 Correct 1 ms 6616 KB Output is correct
9 Correct 2 ms 6616 KB Output is correct
10 Correct 1 ms 6612 KB Output is correct
11 Correct 2 ms 6616 KB Output is correct
12 Correct 1 ms 6616 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6672 KB Output is correct
2 Correct 13 ms 7496 KB Output is correct
3 Correct 123 ms 12536 KB Output is correct
4 Correct 95 ms 12304 KB Output is correct
5 Runtime error 102 ms 21676 KB Execution killed with signal 6
6 Halted 0 ms 0 KB -

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7284 KB Output is correct
2 Correct 30 ms 7780 KB Output is correct
3 Correct 27 ms 8368 KB Output is correct
4 Correct 69 ms 11968 KB Output is correct
5 Correct 71 ms 11964 KB Output is correct
6 Correct 102 ms 11956 KB Output is correct
7 Correct 122 ms 12032 KB Output is correct
8 Correct 100 ms 11964 KB Output is correct
9 Correct 96 ms 11968 KB Output is correct

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6668 KB Output is correct
2 Correct 13 ms 7272 KB Output is correct
3 Correct 66 ms 11156 KB Output is correct
4 Correct 125 ms 12492 KB Output is correct
5 Correct 91 ms 12440 KB Output is correct
6 Correct 77 ms 12184 KB Output is correct
7 Correct 88 ms 12308 KB Output is correct
8 Correct 80 ms 12188 KB Output is correct
9 Correct 99 ms 12784 KB Output is correct
10 Correct 102 ms 12560 KB Output is correct
11 Runtime error 107 ms 21436 KB Execution killed with signal 6
12 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

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