oj.uz

Submission #879569

# Submission time Handle Problem Language Result Execution time Memory
879569 2023-11-27T16:27:35 Z andrei_boaca Highway Tolls (IOI18_highway) C++17
18 / 100
 801 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=rng()%n;
    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;
    if(nivS==nivT)
    {
        vector<int> cand;
        for(int i=0;i<n;i++)
            if(niv[i]==nivS)
                cand.push_back(i);
        while(true)
        {
            if(cand.size()==2)
            {
                c1.push_back(cand[0]);
                c2.push_back(cand[1]);
                break;
            }
            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==1LL*(dist-2)*B+2LL*A)
            {
                cand=x;
                continue;
            }
            if(val==dist*B)
            {
                cand=y;
                continue;
            }
            c1=x;
            c2=y;
            break;
        }
    }
    else
    {
        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);
    if(nivS!=nivT)
    {
        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++)
      |                     ~^~~~~~~~~~~~
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:178:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  178 |             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 12760 KB Output is correct
7 Correct 2 ms 12776 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 9 ms 13580 KB Output is correct
3 Correct 95 ms 20044 KB Output is correct
4 Correct 88 ms 20052 KB Output is correct
5 Correct 86 ms 19820 KB Output is correct
6 Correct 104 ms 20272 KB Output is correct
7 Correct 84 ms 20044 KB Output is correct
8 Correct 90 ms 19820 KB Output is correct
9 Correct 96 ms 19820 KB Output is correct
10 Correct 101 ms 20068 KB Output is correct
11 Correct 105 ms 21084 KB Output is correct
12 Correct 109 ms 21316 KB Output is correct
13 Correct 106 ms 21404 KB Output is correct
14 Correct 103 ms 21164 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14004 KB Output is correct
2 Correct 20 ms 15512 KB Output is correct
3 Correct 28 ms 16764 KB Output is correct
4 Correct 76 ms 24172 KB Output is correct
5 Correct 72 ms 24632 KB Output is correct
6 Correct 80 ms 24000 KB Output is correct
7 Correct 76 ms 23488 KB Output is correct
8 Correct 77 ms 23636 KB Output is correct
9 Correct 75 ms 24304 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 9 ms 13584 KB Output is correct
3 Correct 60 ms 18368 KB Output is correct
4 Correct 95 ms 20068 KB Output is correct
5 Correct 84 ms 19836 KB Output is correct
6 Correct 84 ms 19836 KB Output is correct
7 Correct 91 ms 19828 KB Output is correct
8 Correct 86 ms 20064 KB Output is correct
9 Correct 90 ms 20068 KB Output is correct
10 Correct 127 ms 20288 KB Output is correct
11 Correct 116 ms 21220 KB Output is correct
12 Correct 113 ms 21192 KB Output is correct
13 Correct 105 ms 20860 KB Output is correct
14 Correct 109 ms 21436 KB Output is correct
15 Correct 81 ms 19992 KB Output is correct
16 Correct 85 ms 20052 KB Output is correct
17 Correct 108 ms 20880 KB Output is correct
18 Correct 105 ms 21104 KB Output is correct
19 Correct 133 ms 19820 KB Output is correct
20 Correct 116 ms 21900 KB Output is correct
21 Correct 92 ms 21220 KB Output is correct
22 Correct 76 ms 20980 KB Output is correct
23 Correct 90 ms 20940 KB Output is correct
24 Correct 105 ms 21220 KB Output is correct
25 Runtime error 131 ms 44856 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 801 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 521 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -