oj.uz

Submission #879555

# Submission time Handle Problem Language Result Execution time Memory
879555 2023-11-27T16:16:29 Z andrei_boaca Highway Tolls (IOI18_highway) C++17
0 / 100
 745 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;
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;
    int root=rng()%n;
    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);
    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-1;
    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));
    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;
            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:69:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |         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:170:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  170 |             for(int i=0;i<cand.size();i++)
      |                         ~^~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 12888 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12888 KB Output is correct
2 Correct 11 ms 13672 KB Output is correct
3 Correct 108 ms 19748 KB Output is correct
4 Correct 109 ms 19512 KB Output is correct
5 Correct 119 ms 19272 KB Output is correct
6 Correct 87 ms 19500 KB Output is correct
7 Correct 93 ms 19512 KB Output is correct
8 Correct 125 ms 19732 KB Output is correct
9 Correct 109 ms 19516 KB Output is correct
10 Correct 99 ms 19748 KB Output is correct
11 Correct 108 ms 20056 KB Output is correct
12 Correct 159 ms 20924 KB Output is correct
13 Runtime error 161 ms 20280 KB Execution killed with signal 13
14 Halted 0 ms 0 KB -

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14272 KB Output is correct
2 Runtime error 25 ms 15116 KB Execution killed with signal 13
3 Halted 0 ms 0 KB -

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12888 KB Output is correct
2 Correct 10 ms 13664 KB Output is correct
3 Correct 86 ms 18472 KB Output is correct
4 Correct 97 ms 19508 KB Output is correct
5 Correct 90 ms 19272 KB Output is correct
6 Correct 111 ms 19740 KB Output is correct
7 Correct 101 ms 19744 KB Output is correct
8 Correct 128 ms 19512 KB Output is correct
9 Correct 111 ms 19996 KB Output is correct
10 Correct 98 ms 19732 KB Output is correct
11 Correct 120 ms 20500 KB Output is correct
12 Runtime error 123 ms 21156 KB Execution killed with signal 13
13 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

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