oj.uz

Submission #836253

# Submission time Handle Problem Language Result Execution time Memory
836253 2023-08-24T09:14:21 Z mousebeaver Highway Tolls (IOI18_highway) C++14
12 / 100
 114 ms 11856 KB 
#define ll long long
#define pll pair<ll, ll>
#include "highway.h"
#include <bits/stdc++.h>
using namespace std;

void dfs(vector<vector<pll>>& adjlist, vector<ll>& depth, vector<int>& upedge, int i)
{
    for(pll p : adjlist[i])
    {
        if(depth[p.first] == -1)
        {
            depth[p.first] = depth[i]+1;
            upedge[p.first] = p.second;
            dfs(adjlist, depth, upedge, p.first);
        }
    }
}

void find_pair(int n, std::vector<int> u, std::vector<int> v, int a, int b) 
{
    vector<vector<pll>> adjlist(n, vector<pll> (0));
    for(ll i = 0; i < n-1; i++)
    {
        adjlist[u[i]].push_back({v[i], i});
        adjlist[v[i]].push_back({u[i], i});
    }

    vector<ll> depth(n, -1);
    depth[0] = 0;
    vector<int> upedge(n, -1);
    dfs(adjlist, depth, upedge, 0);

    vector<int> w(n-1, 0);
    ll dist = ask(w)/a;
    vector<ll> c(0);
    for(ll i = 0; i < n; i++)
    {
        if(depth[i] == dist)
        {
            c.push_back(i);
        }
    }

    while(c.size() > 1)
    {
        int mid = (c.size())/2;
        w.assign(n-1, 0);
        for(int i = mid; i < (int) c.size(); i++)
        {
            w[upedge[c[i]]] = 1;
        }

        if(ask(w) > dist*a)
        {
            vector<ll> s(0);
            for(int i = mid; i < (int) c.size(); i++)
            {
                s.push_back(c[i]);
            }
            c = s;
        }
        else
        {
            vector<ll> s(0);
            for(int i = 0; i < mid; i++)
            {
                s.push_back(c[i]);
            }
            c = s;
        }
    }
    answer(0, c[0]);
}

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 7 ms 1376 KB Output is correct
3 Correct 63 ms 10072 KB Output is correct
4 Correct 67 ms 10296 KB Output is correct
5 Correct 114 ms 10076 KB Output is correct
6 Correct 70 ms 9916 KB Output is correct
7 Correct 67 ms 9968 KB Output is correct
8 Correct 60 ms 10056 KB Output is correct
9 Correct 83 ms 9824 KB Output is correct
10 Correct 67 ms 10056 KB Output is correct
11 Correct 65 ms 11224 KB Output is correct
12 Correct 68 ms 11856 KB Output is correct
13 Correct 78 ms 11280 KB Output is correct
14 Correct 64 ms 10844 KB Output is correct

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 1872 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 1 ms 336 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 6 ms 1360 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 1356 KB Incorrect
2 Halted 0 ms 0 KB -