oj.uz

Submission #880631

# Submission time Handle Problem Language Result Execution time Memory
880631 2023-11-29T18:22:18 Z andrei_boaca Highway Tolls (IOI18_highway) C++17
69 / 100
 555 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;
}
int where[100005];
int makesets()
{
    for(int i=0;i<m;i++)
    {
        int a=g[i].first;
        int b=g[i].second;
        if(where[a]==where[b])
            w[i]=1;
        else
            w[i]=0;
    }
    return ask(w);
}
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});
    }
    if(A==1&&B==2)
    {
        w.resize(m);
        int xx=0;
        for(int bit=0;bit<17;bit++)
        {
            for(int i=0;i<n;i++)
            {
                if((i>>bit)&1)
                    where[i]=0;
                else
                    where[i]=1;
            }
            int d=makesets();
            if(d%2==1)
                xx^=(1<<bit);
        }
        vector<pii> vv;
        for(int a=0;a<n;a++)
        {
            int b=(a^xx);
            if(b>a)
                vv.push_back({a,b});
        }
        int st=0;
        int dr=vv.size()-1;
        int S=0,T=0;
        while(st<=dr)
        {
            int mij=(st+dr)/2;
            for(int i=0;i<vv.size();i++)
            {
                int a=vv[i].first;
                int b=vv[i].second;
                if(i<=mij)
                {
                    where[a]=0;
                    where[b]=1;
                }
                else
                {
                    where[a]=0;
                    where[b]=0;
                }
            }
            int d=makesets();
            if(d%2==1)
            {
                S=vv[mij].first;
                T=vv[mij].second;
                dr=mij-1;
            }
            else
                st=mij+1;
        }
        answer(S,T);
        return;
    }
    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 val=buildniv(mij);
        if(val==dist*A)
        {
            nivT=mij+1;
            dr=mij-1;
        }
        else
            st=mij+1;
    }
    nivS=nivlca+(dist-(nivT-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++)
      |                     ~^~~~~~~~~~~~
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:154:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  154 |             for(int i=0;i<vv.size();i++)
      |                         ~^~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4440 KB Output is correct
2 Correct 3 ms 12632 KB Output is correct
3 Correct 3 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 2 ms 12632 KB Output is correct
10 Correct 2 ms 12632 KB Output is correct
11 Correct 2 ms 12736 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 12788 KB Output is correct
2 Correct 15 ms 13700 KB Output is correct
3 Correct 99 ms 20412 KB Output is correct
4 Correct 101 ms 20892 KB Output is correct
5 Correct 112 ms 20624 KB Output is correct
6 Correct 114 ms 20432 KB Output is correct
7 Correct 145 ms 20652 KB Output is correct
8 Correct 97 ms 20644 KB Output is correct
9 Correct 127 ms 20204 KB Output is correct
10 Correct 112 ms 20644 KB Output is correct
11 Correct 117 ms 11444 KB Output is correct
12 Correct 101 ms 21624 KB Output is correct
13 Correct 113 ms 21000 KB Output is correct
14 Correct 93 ms 21248 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 14084 KB Output is correct
2 Correct 19 ms 15664 KB Output is correct
3 Correct 27 ms 16912 KB Output is correct
4 Correct 74 ms 23560 KB Output is correct
5 Correct 79 ms 23736 KB Output is correct
6 Correct 75 ms 25172 KB Output is correct
7 Correct 109 ms 24312 KB Output is correct
8 Correct 73 ms 23516 KB Output is correct
9 Correct 92 ms 23388 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4876 KB Output is correct
2 Correct 12 ms 13696 KB Output is correct
3 Correct 65 ms 18668 KB Output is correct
4 Correct 85 ms 20408 KB Output is correct
5 Correct 82 ms 20404 KB Output is correct
6 Correct 105 ms 20168 KB Output is correct
7 Correct 92 ms 20644 KB Output is correct
8 Correct 105 ms 20160 KB Output is correct
9 Correct 119 ms 20428 KB Output is correct
10 Correct 95 ms 20204 KB Output is correct
11 Correct 146 ms 21076 KB Output is correct
12 Correct 118 ms 21132 KB Output is correct
13 Correct 91 ms 21232 KB Output is correct
14 Correct 107 ms 21472 KB Output is correct
15 Correct 84 ms 12288 KB Output is correct
16 Correct 86 ms 20396 KB Output is correct
17 Correct 131 ms 21128 KB Output is correct
18 Correct 100 ms 21380 KB Output is correct
19 Correct 104 ms 20404 KB Output is correct
20 Correct 124 ms 21940 KB Output is correct
21 Correct 86 ms 21904 KB Output is correct
22 Correct 86 ms 21672 KB Output is correct
23 Correct 112 ms 21284 KB Output is correct
24 Correct 147 ms 21764 KB Output is correct
25 Correct 123 ms 11292 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 5512 KB Output is correct
2 Correct 15 ms 5404 KB Output is correct
3 Correct 121 ms 12472 KB Output is correct
4 Correct 106 ms 12860 KB Output is correct
5 Correct 133 ms 14384 KB Output is correct
6 Correct 148 ms 14444 KB Output is correct
7 Correct 156 ms 14060 KB Output is correct
8 Correct 119 ms 14280 KB Output is correct
9 Correct 115 ms 12256 KB Output is correct
10 Correct 113 ms 12624 KB Output is correct
11 Correct 130 ms 12964 KB Output is correct
12 Correct 119 ms 13852 KB Output is correct
13 Correct 112 ms 13600 KB Output is correct
14 Correct 121 ms 14076 KB Output is correct
15 Correct 113 ms 14300 KB Output is correct
16 Correct 153 ms 12896 KB Output is correct
17 Correct 103 ms 12740 KB Output is correct
18 Correct 87 ms 12328 KB Output is correct
19 Correct 81 ms 12380 KB Output is correct
20 Correct 83 ms 12556 KB Output is correct
21 Correct 114 ms 14524 KB Output is correct

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Runtime error 555 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -