oj.uz

Submission #879575

# Submission time Handle Problem Language Result Execution time Memory
879575 2023-11-27T16:31:33 Z andrei_boaca Highway Tolls (IOI18_highway) C++17
18 / 100
 741 ms 262144 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;
ll dist,AA,BB;
vector<pii> muchii[100005];
vector<pii> g;
vector<int> w;
ll memo[100005],calls;
bool isancestor(int a,int b)
{
    return in[a]<=in[b]&&out[a]>=out[b];
}
int LCA(int a,int b)
{
    if(niv[a]>niv[b])
        swap(a,b);
    if(isancestor(a,b))
        return a;
    for(int i=20;i>=0;i--)
        if(dp[i][a]!=-1&&!isancestor(dp[i][a],b))
            a=dp[i][a];
    return par[a];
}
void dfs(int nod)
{
    timp++;
    in[nod]=timp;
    dp[0][nod]=par[nod];
    for(int i=1;i<=20;i++)
    {
        if(dp[i-1][nod]==-1)
        {
            dp[i][nod]=-1;
            continue;
        }
        dp[i][nod]=dp[i-1][dp[i-1][nod]];
    }
    for(auto i:muchii[nod])
        if(i.first!=par[nod])
        {
            par[i.first]=nod;
            niv[i.first]=niv[nod]+1;
            topar[i.first]=i.second;
            dfs(i.first);
        }
    out[nod]=timp;
}
ll buildniv(int p)
{
    if(memo[p]!=0)
        return memo[p];
    for(int i=0;i<m;i++)
    {
        w[i]=1;
        if(min(niv[g[i].first],niv[g[i].second])<=p)
            w[i]=0;
    }
    calls++;
    assert(calls<=60);
    memo[p]=ask(w);
    return memo[p];
}
int getnode(vector<int> cand)
{
    while(true)
    {
        if(cand.size()==1)
            return cand[0];
        vector<int> x,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<m;i++)
            w[i]=1;
        for(int i:x)
            w[topar[i]]=0;
        calls++;
        assert(calls<=60);
        ll val=ask(w);
        if(val<dist*BB)
            cand=x;
        else
            cand=y;
    }
    return -1;
}
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});
    }
    for(int i=0;i<n;i++)
        par[i]=-1;
    int root=0;
    niv[root]=1;
    dfs(root);
    int nivmax=0;
    for(int i=0;i<n;i++)
        nivmax=max(nivmax,niv[i]);
    for(int i=0;i<m;i++)
        w.push_back(0);
    calls++;
    assert(calls<=60);
    dist=ask(w)/A;
    int nivlca=nivmax;
    int st=1;
    int dr=nivmax-1;
    while(st<=dr)
    {
        int mij=(st+dr)/2;
        ll val=buildniv(mij);
        if(val<dist*B)
        {
            nivlca=mij;
            dr=mij-1;
        }
        else
            st=mij+1;
    }
    int nivS=nivlca;
    int nivT=0;
    st=nivlca;
    dr=nivmax-1;
    while(st<=dr)
    {
        int mij=(st+dr)/2;
        ll nra=2*(mij-nivlca);
        if(nra<=dist)
        {
            ll val=buildniv(mij);
            ll val2=buildniv(mij-1);
            if(val2==val+2LL*(B-A))
            {
                nivS=mij+1;
                st=mij+1;
                continue;
            }
        }
        dr=mij-1;
    }
    nivT=nivlca+(dist-(nivS-nivlca));
    //assert(nivS<=nivT);
    vector<int> c1,c2;
    for(int i=0;i<n;i++)
    {
        if(niv[i]==nivS)
            c1.push_back(i);
        if(niv[i]==nivT)
            c2.push_back(i);
    }
    int T=getnode(c2);
    c1.clear();
    for(int i=0;i<n;i++)
        if(niv[i]==nivS&&niv[LCA(i,T)]==nivlca)
            c1.push_back(i);
    int S=getnode(c1);
    //assert(S!=T);
    //assert(S!=-1&&T!=-1);
    answer(S,T);
}

Compilation message

highway.cpp: In function 'int getnode(std::vector<int>)':
highway.cpp:76:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |         for(int i=0;i<cand.size();i++)
      |                     ~^~~~~~~~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12632 KB Output is correct
2 Correct 15 ms 13652 KB Output is correct
3 Correct 125 ms 20052 KB Output is correct
4 Correct 84 ms 19932 KB Output is correct
5 Correct 87 ms 19816 KB Output is correct
6 Correct 97 ms 20048 KB Output is correct
7 Correct 95 ms 19820 KB Output is correct
8 Correct 110 ms 19812 KB Output is correct
9 Correct 85 ms 20024 KB Output is correct
10 Correct 94 ms 19820 KB Output is correct
11 Correct 93 ms 21116 KB Output is correct
12 Correct 106 ms 21600 KB Output is correct
13 Correct 96 ms 20772 KB Output is correct
14 Correct 125 ms 20448 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 14224 KB Output is correct
2 Correct 20 ms 15508 KB Output is correct
3 Correct 36 ms 16952 KB Output is correct
4 Correct 121 ms 25144 KB Output is correct
5 Correct 70 ms 24904 KB Output is correct
6 Correct 121 ms 24932 KB Output is correct
7 Correct 70 ms 24904 KB Output is correct
8 Correct 130 ms 24896 KB Output is correct
9 Correct 106 ms 24916 KB Output is correct

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12632 KB Output is correct
2 Correct 11 ms 13580 KB Output is correct
3 Correct 69 ms 18388 KB Output is correct
4 Correct 77 ms 19824 KB Output is correct
5 Correct 136 ms 20720 KB Output is correct
6 Correct 86 ms 19816 KB Output is correct
7 Correct 74 ms 20292 KB Output is correct
8 Correct 90 ms 20064 KB Output is correct
9 Correct 90 ms 20280 KB Output is correct
10 Correct 135 ms 19820 KB Output is correct
11 Correct 103 ms 20584 KB Output is correct
12 Correct 117 ms 21576 KB Output is correct
13 Correct 110 ms 21364 KB Output is correct
14 Correct 119 ms 21760 KB Output is correct
15 Correct 120 ms 19816 KB Output is correct
16 Correct 106 ms 20076 KB Output is correct
17 Correct 109 ms 21244 KB Output is correct
18 Correct 127 ms 21360 KB Output is correct
19 Correct 77 ms 20056 KB Output is correct
20 Correct 168 ms 22424 KB Output is correct
21 Correct 118 ms 21316 KB Output is correct
22 Correct 126 ms 21308 KB Output is correct
23 Correct 125 ms 20708 KB Output is correct
24 Correct 102 ms 21512 KB Output is correct
25 Runtime error 128 ms 48408 KB Execution killed with signal 6
26 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 741 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Runtime error 552 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -