oj.uz

Submission #879547

# Submission time Handle Problem Language Result Execution time Memory
879547 2023-11-27T16:03:40 Z andrei_boaca Highway Tolls (IOI18_highway) C++17
18 / 100
 777 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;
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;
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;
}
void buildniv(int 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;
    }
}
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;
        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;
    niv[0]=1;
    dfs(0);
    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);
    dist=ask(w)/A;
    int nivlca=nivmax;
    int st=1;
    int dr=nivmax-1;
    while(st<=dr)
    {
        int mij=(st+dr)/2;
        buildniv(mij);
        ll val=ask(w);
        if(val<dist*B)
        {
            nivlca=mij;
            dr=mij-1;
        }
        else
            st=mij+1;
    }
    int nivS=nivlca;
    int nivT=0;
    st=nivlca;
    dr=nivmax;
    while(st<=dr)
    {
        int mij=(st+dr)/2;
        buildniv(mij);
        ll nra=2*(mij-nivlca);
        if(nra<=dist)
        {
            ll val=ask(w);
            buildniv(mij-1);
            ll val2=ask(w);
            if(val2==val+2LL*(B-A))
            {
                nivS=mij+1;
                st=mij+1;
                continue;
            }
        }
        dr=mij-1;
    }
    nivT=nivlca+(dist-(nivS-nivlca));
    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;
            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);
    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);
    answer(S,T);
}

Compilation message

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

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12888 KB Output is correct
2 Correct 13 ms 13640 KB Output is correct
3 Correct 91 ms 19272 KB Output is correct
4 Correct 92 ms 19972 KB Output is correct
5 Correct 96 ms 19264 KB Output is correct
6 Correct 108 ms 19264 KB Output is correct
7 Correct 107 ms 19492 KB Output is correct
8 Correct 87 ms 19344 KB Output is correct
9 Correct 89 ms 19300 KB Output is correct
10 Correct 93 ms 19288 KB Output is correct
11 Correct 95 ms 20320 KB Output is correct
12 Correct 113 ms 20908 KB Output is correct
13 Correct 92 ms 20436 KB Output is correct
14 Correct 130 ms 20124 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 14380 KB Output is correct
2 Correct 19 ms 15496 KB Output is correct
3 Correct 36 ms 16684 KB Output is correct
4 Correct 79 ms 24648 KB Output is correct
5 Correct 74 ms 24596 KB Output is correct
6 Correct 77 ms 24348 KB Output is correct
7 Correct 105 ms 24340 KB Output is correct
8 Correct 83 ms 24340 KB Output is correct
9 Correct 76 ms 24596 KB Output is correct

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12888 KB Output is correct
2 Correct 11 ms 13632 KB Output is correct
3 Correct 78 ms 17972 KB Output is correct
4 Correct 128 ms 19492 KB Output is correct
5 Correct 94 ms 19264 KB Output is correct
6 Correct 79 ms 19744 KB Output is correct
7 Correct 102 ms 19500 KB Output is correct
8 Correct 93 ms 19968 KB Output is correct
9 Correct 90 ms 19504 KB Output is correct
10 Correct 86 ms 19284 KB Output is correct
11 Correct 149 ms 20000 KB Output is correct
12 Correct 164 ms 21220 KB Output is correct
13 Correct 140 ms 21004 KB Output is correct
14 Correct 111 ms 21400 KB Output is correct
15 Correct 82 ms 19496 KB Output is correct
16 Correct 86 ms 19284 KB Output is correct
17 Correct 125 ms 21120 KB Output is correct
18 Correct 112 ms 20576 KB Output is correct
19 Correct 100 ms 19268 KB Output is correct
20 Correct 113 ms 21408 KB Output is correct
21 Correct 84 ms 20532 KB Output is correct
22 Correct 85 ms 20504 KB Output is correct
23 Incorrect 110 ms 21160 KB Output isn't correct
24 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 777 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 512 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -