oj.uz

Submission #881538

# Submission time Handle Problem Language Result Execution time Memory
881538 2023-12-01T12:14:07 Z andrei_boaca Highway Tolls (IOI18_highway) C++17
7 / 100
 168 ms 15824 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;
        w[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)
            {
                if(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);
                }
                else if(d[ind][i.first]==d[ind][nod]+1)
                    w[i.second]=1;
            }
            else if(i.first!=roots[3-ind])
                w[i.second]=1;
        }
    }
    //sort(edges.begin(),edges.end(),byniv);
    /*ll val=ask(w);
    if(val==dist*BB)
        return roots[ind];*/
    ll st=0;
    ll dr=edges.size();
    dr--;
    ll ans=-1;
    int poz=0;
    while(st<=dr)
    {
        ll mij=(st+dr)/2;
        for(int i:edges)
            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;
        }
    }
    if(ans==-1)
        return roots[ind];
    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:124:9: warning: variable 'poz' set but not used [-Wunused-but-set-variable]
  124 |     int poz=0;
      |         ^~~

Subtask #1
0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6676 KB Output is correct
2 Correct 13 ms 7388 KB Output is correct
3 Correct 89 ms 13836 KB Output is correct
4 Correct 113 ms 13624 KB Output is correct
5 Correct 87 ms 13756 KB Output is correct
6 Correct 125 ms 13440 KB Output is correct
7 Correct 86 ms 13868 KB Output is correct
8 Correct 85 ms 13544 KB Output is correct
9 Correct 98 ms 13604 KB Output is correct
10 Correct 89 ms 13624 KB Output is correct
11 Correct 117 ms 12868 KB Output is correct
12 Correct 92 ms 12988 KB Output is correct
13 Correct 95 ms 12808 KB Output is correct
14 Correct 149 ms 12792 KB Output is correct

Subtask #3
0 / 6.0

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

Subtask #4
0 / 33.0

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

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 7336 KB Output is correct
2 Correct 16 ms 7456 KB Output is correct
3 Correct 142 ms 13816 KB Output is correct
4 Correct 107 ms 14424 KB Output is correct
5 Correct 130 ms 15824 KB Output is correct
6 Correct 112 ms 15732 KB Output is correct
7 Correct 168 ms 15248 KB Output is correct
8 Incorrect 127 ms 15416 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 12 ms 7384 KB Output is correct
2 Correct 13 ms 7528 KB Output is correct
3 Correct 111 ms 13912 KB Output is correct
4 Correct 137 ms 14140 KB Output is correct
5 Correct 134 ms 14316 KB Output is correct
6 Incorrect 160 ms 15444 KB Output is incorrect: {s, t} is wrong.
7 Halted 0 ms 0 KB -