oj.uz

Submission #881533

# Submission time Handle Problem Language Result Execution time Memory
881533 2023-12-01T12:05:41 Z andrei_boaca Highway Tolls (IOI18_highway) C++17
51 / 100
 155 ms 15968 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],roots[5];
ll dist,AA,BB,d[3][100005];
int where[100005];
vector<pii> muchii[100005];
vector<pii> g;
vector<int> w;
ll memo[100005],calls;
bool inarb[300005],inx[300005];
int IND;
void bfs(int ind)
{
    for(int i=0;i<n;i++)
        d[ind][i]=1e9;
    d[ind][roots[ind]]=0;
    queue<int> coada;
    coada.push(roots[ind]);
    while(!coada.empty())
    {
        int nod=coada.front();
        coada.pop();
        for(auto i:muchii[nod])
            if(d[ind][i.first]>d[ind][nod]+1)
            {
                d[ind][i.first]=d[ind][nod]+1;
                coada.push(i.first);
            }
    }
}
ll buildniv(ll nivmax,ll ind)
{
    for(int i=0;i<m;i++)
    {
        if(inarb[i]==0)
        {
            w[i]=1;
            continue;
        }
        int a=g[i].first,b=g[i].second;
        if(max(d[ind][a],d[ind][b])<=nivmax)
            w[i]=0;
        else
            w[i]=1;
    }
    return ask(w);
}
ll buildx(int ind)
{
    for(int i=0;i<m;i++)
    {
        if(inarb[i]==0)
        {
            w[i]=1;
            continue;
        }
        int a=g[i].first,b=g[i].second;
        if(d[ind][a]<d[ind][b])
            swap(a,b);
        if(inx[a])
            w[i]=0;
        else
            w[i]=1;
    }
    return ask(w);
}
bool byniv(int i,int j)
{
    int a=max(d[IND][g[i].first],d[IND][g[i].second]);
    int b=max(d[IND][g[j].first],d[IND][g[j].second]);
    return a<b;
}
int plsfind(int ind)
{
    IND=ind;
    for(int i=0;i<m;i++)
        inarb[i]=0;
    for(int i=0;i<n;i++)
        d[ind][i]=1e9;
    ll nivmax=0;
    d[ind][roots[ind]]=0;
    queue<int> coada;
    coada.push(roots[ind]);
    vector<int> edges;
    while(!coada.empty())
    {
        int nod=coada.front();
        nivmax=max(nivmax,d[ind][nod]);
        coada.pop();
        for(auto i:muchii[nod])
            if(where[i.first]==ind&&d[ind][i.first]>d[ind][nod]+1)
            {
                d[ind][i.first]=d[ind][nod]+1;
                inarb[i.second]=1;
                edges.push_back(i.second);
                coada.push(i.first);
            }
    }
    //sort(edges.begin(),edges.end(),byniv);
    for(int i=0;i<m;i++)
        w[i]=1;
    for(int j:edges)
        w[j]=0;
    ll val=ask(w);
    if(val==dist*BB)
        return roots[ind];
    ll st=0;
    ll dr=edges.size();
    dr--;
    ll ans=0;
    int poz=0;
    while(st<=dr)
    {
        ll mij=(st+dr)/2;
        for(int i=0;i<m;i++)
            {
                ll a=g[i].first,b=g[i].second;
                if(a==roots[1]&&b==roots[2])
                {
                    w[i]=0;
                    continue;
                }
                if(a==roots[2]&&b==roots[1])
                {
                    w[i]=0;
                    continue;
                }
                if(where[a]!=where[b])
                {
                    w[i]=1;
                    continue;
                }
                if(where[a]!=ind)
                {
                    w[i]=0;
                    continue;
                }
                w[i]=1;
            }
        for(int j=0;j<=mij;j++)
            w[edges[j]]=0;
        ll x=ask(w);
        int p=edges[mij];
        int a=g[p].first;
        int b=g[p].second;
        if(x!=dist*AA)
            st=mij+1;
        else
        {
            poz=mij;
            if(d[ind][a]<d[ind][b])
                swap(a,b);
            ans=a;
            dr=mij-1;
        }
    }
    return ans;
}
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});
    }
    w.resize(m);
    dist=ask(w)/A;
    ll st=0;
    ll dr=m-1;
    while(st<=dr)
    {
        ll mij=(st+dr)/2;
        for(int i=0;i<m;i++)
        {
            if(i<=mij)
                w[i]=1;
            else
                w[i]=0;
        }
        ll val=ask(w);
        if(val>dist*A)
        {
            roots[1]=g[mij].first;
            roots[2]=g[mij].second;
            dr=mij-1;
        }
        else
            st=mij+1;
    }
    bfs(1);
    bfs(2);
    for(int i=0;i<n;i++)
    {
        if(d[1][i]<d[2][i])
            where[i]=1;
        if(d[2][i]<d[1][i])
            where[i]=2;
    }
    int S=plsfind(1);
    int T=plsfind(2);
    answer(S,T);
}

Compilation message

highway.cpp: In function 'int plsfind(int)':
highway.cpp:116:9: warning: variable 'poz' set but not used [-Wunused-but-set-variable]
  116 |     int poz=0;
      |         ^~~

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6676 KB Output is correct
2 Correct 10 ms 7464 KB Output is correct
3 Correct 90 ms 13612 KB Output is correct
4 Correct 97 ms 13392 KB Output is correct
5 Correct 97 ms 13404 KB Output is correct
6 Correct 87 ms 13392 KB Output is correct
7 Correct 93 ms 13640 KB Output is correct
8 Correct 93 ms 13376 KB Output is correct
9 Correct 82 ms 13380 KB Output is correct
10 Correct 96 ms 14084 KB Output is correct
11 Correct 92 ms 12900 KB Output is correct
12 Correct 92 ms 12972 KB Output is correct
13 Correct 100 ms 13264 KB Output is correct
14 Correct 91 ms 12784 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7388 KB Output is correct
2 Correct 15 ms 7936 KB Output is correct
3 Correct 24 ms 8616 KB Output is correct
4 Correct 66 ms 12468 KB Output is correct
5 Correct 68 ms 12676 KB Output is correct
6 Correct 69 ms 12960 KB Output is correct
7 Correct 66 ms 12916 KB Output is correct
8 Correct 64 ms 12700 KB Output is correct
9 Correct 65 ms 12724 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6672 KB Output is correct
2 Correct 12 ms 7612 KB Output is correct
3 Correct 60 ms 12216 KB Output is correct
4 Correct 80 ms 13528 KB Output is correct
5 Correct 80 ms 13672 KB Output is correct
6 Correct 77 ms 13508 KB Output is correct
7 Correct 69 ms 13400 KB Output is correct
8 Correct 77 ms 13384 KB Output is correct
9 Correct 98 ms 14096 KB Output is correct
10 Correct 87 ms 13584 KB Output is correct
11 Correct 88 ms 13040 KB Output is correct
12 Correct 93 ms 12996 KB Output is correct
13 Correct 91 ms 12992 KB Output is correct
14 Correct 96 ms 12668 KB Output is correct
15 Correct 83 ms 13844 KB Output is correct
16 Correct 82 ms 14104 KB Output is correct
17 Correct 90 ms 13272 KB Output is correct
18 Correct 94 ms 13288 KB Output is correct
19 Correct 77 ms 13640 KB Output is correct
20 Correct 92 ms 13128 KB Output is correct
21 Correct 78 ms 13812 KB Output is correct
22 Correct 74 ms 14040 KB Output is correct
23 Correct 86 ms 13148 KB Output is correct
24 Correct 84 ms 13560 KB Output is correct
25 Correct 89 ms 12888 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 7404 KB Output is correct
2 Correct 13 ms 7480 KB Output is correct
3 Correct 101 ms 14492 KB Output is correct
4 Correct 129 ms 14428 KB Output is correct
5 Correct 139 ms 15604 KB Output is correct
6 Correct 133 ms 15968 KB Output is correct
7 Correct 142 ms 15920 KB Output is correct
8 Incorrect 155 ms 15772 KB Output is incorrect: {s, t} is wrong.
9 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 7312 KB Output is correct
2 Correct 13 ms 7528 KB Output is correct
3 Correct 116 ms 14192 KB Output is correct
4 Correct 120 ms 13936 KB Output is correct
5 Correct 127 ms 14556 KB Output is correct
6 Incorrect 150 ms 15772 KB Output is incorrect: {s, t} is wrong.
7 Halted 0 ms 0 KB -