oj.uz

Submission #1060051

# Submission time Handle Problem Language Result Execution time Memory
1060051 2024-08-15T10:17:42 Z jerzyk Highway Tolls (IOI18_highway) C++17
0 / 100
 20 ms 50264 KB 
#include <bits/stdc++.h>
#include "highway.h"

using namespace std;
#define pb push_back
#define st first
#define nd second
typedef long long ll;
typedef long double ld;
const ll I = 1000LL * 1000LL * 1000LL * 1000LL * 1000LL * 1000LL;
const int II = 1000 * 1000 * 1000 * 2;
const ll M = 1000LL * 1000LL * 1000LL + 7LL;
const int N = 1000 * 1000 + 7;
ll bas, A, B;
vector<int>ed[N], num[N];
vector<int> cnd;
int dis[N];
vector<int> cur;

bool Question(int pos)
{
    for(int i = pos; i < (int)cur.size(); ++i)
    {
        int v = cur[i];
        for(int j = 0; j < (int)num[v].size(); ++j)
            cnd[num[v][j]] = 1;
    }
    ll ans = ask(cnd);
    for(int i = 0; i < (int)cnd.size(); ++i)
        cnd[i] = 0;
    return (ans > bas);
}

int BS()
{
    int p = 0, k = (int)cur.size(), s;
    while(p < k)
    {
        s = (p + k + 1) / 2;
        if(Question(s))
            p = s;
        else
            k = s - 1;
    }
    return cur[p];
}

void BFS(int s, int n)
{
    int v; queue<int> q;
    for(int i = 0; i <= n; ++i)
        dis[i] = II;
    dis[s] = 0;
    while(q.size() > 0)
    {
        v = q.front(); q.pop();
        for(int i = 0; i < (int)ed[v].size(); ++i)
        {
            if(dis[ed[v][i]] > dis[v] + 1)
            {
                dis[ed[v][i]] = dis[v] + 1;
                q.push(ed[v][i]);
            }
        }
    }
}

void DoCur1(int n)
{
    vector<pair<int, int>> hlp;
    for(int i = 0; i < n; ++i)
        hlp.pb(make_pair(dis[i], i));
    sort(hlp.begin(), hlp.end());
    cur.clear();
    for(int i = 0; i < n; ++i)
        cur.pb(hlp[i].nd);
}

void DoCur2(int n, int il)
{
    cur.clear();
    for(int i = 0; i < n; ++i)
        if(dis[i] == il)
            cur.pb(i);
}

void find_pair(int N, vector<int> U, vector<int> V, int XA, int XB)
{
    A = XA; B = XB;
    int n = N;
    for(int i = 0; i < (int)U.size(); ++i)
    {
        ed[U[i]].pb(V[i]); ed[V[i]].pb(U[i]);
        num[U[i]].pb(i); num[V[i]].pb(i);
        cnd.pb(0);
    }
    bas = ask(cnd);
    for(int i = 0; i < n; ++i)
        cur.pb(i);
    int mid = BS(), s, t;
    BFS(mid, n);
    DoCur1(n);
    s = BS();
    BFS(s, n);
    DoCur2(n, bas / A);
    t = BS();
    answer(s, t);
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 48984 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 Incorrect 8 ms 48984 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 17 ms 50008 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 11 ms 49236 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 Incorrect 20 ms 50264 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

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