oj.uz

Submission #879576

# Submission time Handle Problem Language Result Execution time Memory
879576 2023-11-27T16:32:04 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;
    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 12632 KB Output is correct
7 Correct 2 ms 12632 KB Output is correct
8 Correct 2 ms 12632 KB Output is correct
9 Correct 3 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 3 ms 12820 KB Output is correct
2 Correct 16 ms 13652 KB Output is correct
3 Correct 101 ms 20284 KB Output is correct
4 Correct 98 ms 20048 KB Output is correct
5 Correct 86 ms 19816 KB Output is correct
6 Correct 85 ms 19844 KB Output is correct
7 Correct 136 ms 19816 KB Output is correct
8 Correct 75 ms 20180 KB Output is correct
9 Correct 84 ms 19844 KB Output is correct
10 Correct 82 ms 20060 KB Output is correct
11 Correct 114 ms 21024 KB Output is correct
12 Correct 108 ms 21852 KB Output is correct
13 Correct 114 ms 20916 KB Output is correct
14 Correct 119 ms 21116 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 14348 KB Output is correct
2 Correct 19 ms 15552 KB Output is correct
3 Correct 24 ms 16644 KB Output is correct
4 Correct 73 ms 22380 KB Output is correct
5 Correct 83 ms 24668 KB Output is correct
6 Correct 87 ms 22728 KB Output is correct
7 Correct 69 ms 23408 KB Output is correct
8 Correct 76 ms 23580 KB Output is correct
9 Correct 118 ms 23900 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 12 ms 13588 KB Output is correct
3 Correct 107 ms 19108 KB Output is correct
4 Correct 128 ms 19828 KB Output is correct
5 Correct 122 ms 20052 KB Output is correct
6 Correct 85 ms 20052 KB Output is correct
7 Correct 89 ms 19820 KB Output is correct
8 Correct 93 ms 20288 KB Output is correct
9 Correct 139 ms 20056 KB Output is correct
10 Correct 89 ms 20056 KB Output is correct
11 Correct 107 ms 21692 KB Output is correct
12 Correct 100 ms 21396 KB Output is correct
13 Correct 133 ms 21236 KB Output is correct
14 Correct 113 ms 21832 KB Output is correct
15 Correct 118 ms 20304 KB Output is correct
16 Correct 80 ms 20056 KB Output is correct
17 Correct 102 ms 21388 KB Output is correct
18 Correct 155 ms 21088 KB Output is correct
19 Correct 81 ms 20064 KB Output is correct
20 Correct 93 ms 22112 KB Output is correct
21 Correct 115 ms 21500 KB Output is correct
22 Correct 79 ms 21556 KB Output is correct
23 Correct 116 ms 20932 KB Output is correct
24 Correct 96 ms 21260 KB Output is correct
25 Runtime error 129 ms 47820 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 496 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -