oj.uz

Submission #879557

# Submission time Handle Problem Language Result Execution time Memory
879557 2023-11-27T16:17:57 Z andrei_boaca Highway Tolls (IOI18_highway) C++17
7 / 100
 718 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 Correct 2 ms 12888 KB Output is correct
2 Correct 2 ms 12888 KB Output is correct
3 Runtime error 3 ms 12936 KB Execution killed with signal 13
4 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12888 KB Output is correct
2 Correct 11 ms 13664 KB Output is correct
3 Correct 82 ms 19524 KB Output is correct
4 Correct 95 ms 19512 KB Output is correct
5 Correct 113 ms 19268 KB Output is correct
6 Correct 121 ms 19748 KB Output is correct
7 Correct 80 ms 19500 KB Output is correct
8 Correct 122 ms 19292 KB Output is correct
9 Correct 84 ms 19380 KB Output is correct
10 Correct 128 ms 19512 KB Output is correct
11 Correct 106 ms 20464 KB Output is correct
12 Correct 117 ms 21060 KB Output is correct
13 Correct 99 ms 20644 KB Output is correct
14 Correct 107 ms 20272 KB Output is correct

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 14112 KB Output is correct
2 Correct 20 ms 15024 KB Output is correct
3 Correct 31 ms 15884 KB Output is correct
4 Correct 94 ms 22712 KB Output is correct
5 Correct 112 ms 21580 KB Output is correct
6 Runtime error 97 ms 22516 KB Execution killed with signal 13
7 Halted 0 ms 0 KB -

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12888 KB Output is correct
2 Correct 10 ms 13824 KB Output is correct
3 Correct 62 ms 18016 KB Output is correct
4 Correct 82 ms 19748 KB Output is correct
5 Correct 86 ms 19508 KB Output is correct
6 Correct 99 ms 19748 KB Output is correct
7 Correct 86 ms 19784 KB Output is correct
8 Correct 101 ms 20188 KB Output is correct
9 Correct 90 ms 19512 KB Output is correct
10 Correct 87 ms 19276 KB Output is correct
11 Correct 100 ms 20608 KB Output is correct
12 Runtime error 123 ms 20420 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 718 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 531 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -