oj.uz

Submission #879566

# Submission time Handle Problem Language Result Execution time Memory
879566 2023-11-27T16:25:27 Z andrei_boaca Highway Tolls (IOI18_highway) C++17
18 / 100
 771 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 12632 KB Output is correct
7 Correct 2 ms 12632 KB Output is correct
8 Correct 3 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 13580 KB Output is correct
3 Correct 86 ms 20284 KB Output is correct
4 Correct 83 ms 19836 KB Output is correct
5 Correct 85 ms 19816 KB Output is correct
6 Correct 86 ms 19816 KB Output is correct
7 Correct 88 ms 20304 KB Output is correct
8 Correct 90 ms 20052 KB Output is correct
9 Correct 110 ms 20304 KB Output is correct
10 Correct 119 ms 19816 KB Output is correct
11 Correct 134 ms 21624 KB Output is correct
12 Correct 99 ms 20992 KB Output is correct
13 Correct 128 ms 21740 KB Output is correct
14 Correct 134 ms 20692 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 13948 KB Output is correct
2 Correct 28 ms 15128 KB Output is correct
3 Correct 23 ms 15976 KB Output is correct
4 Correct 99 ms 22348 KB Output is correct
5 Correct 67 ms 24100 KB Output is correct
6 Correct 79 ms 22720 KB Output is correct
7 Correct 115 ms 24136 KB Output is correct
8 Correct 108 ms 23368 KB Output is correct
9 Correct 95 ms 24296 KB Output is correct

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12884 KB Output is correct
2 Correct 11 ms 13652 KB Output is correct
3 Correct 59 ms 18368 KB Output is correct
4 Correct 126 ms 19816 KB Output is correct
5 Correct 111 ms 20056 KB Output is correct
6 Correct 117 ms 20272 KB Output is correct
7 Correct 95 ms 19960 KB Output is correct
8 Correct 93 ms 20064 KB Output is correct
9 Correct 96 ms 20296 KB Output is correct
10 Correct 122 ms 20512 KB Output is correct
11 Correct 141 ms 20764 KB Output is correct
12 Correct 132 ms 22036 KB Output is correct
13 Correct 104 ms 21008 KB Output is correct
14 Correct 136 ms 21688 KB Output is correct
15 Correct 81 ms 20056 KB Output is correct
16 Correct 81 ms 19820 KB Output is correct
17 Correct 97 ms 20964 KB Output is correct
18 Correct 106 ms 21836 KB Output is correct
19 Correct 83 ms 19952 KB Output is correct
20 Correct 122 ms 21264 KB Output is correct
21 Correct 101 ms 20788 KB Output is correct
22 Correct 126 ms 20776 KB Output is correct
23 Correct 103 ms 20532 KB Output is correct
24 Correct 103 ms 21576 KB Output is correct
25 Runtime error 162 ms 48396 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 771 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 585 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -