oj.uz

Submission #601844

# Submission time Handle Problem Language Result Execution time Memory
601844 2022-07-22T10:54:03 Z Hanksburger Highway Tolls (IOI18_highway) C++17
51 / 100
 173 ms 14844 KB 
#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
vector<pair<int, int> > adj[90005];
pair<int, int> par[90005];
vector<int> vu, vv, vec;
void dfs(int u, int p, int d, bool b)
{
    if (b)
        vu.push_back(u);
    else
        vv.push_back(u);
    for (int i=0; i<adj[u].size(); i++)
    {
        int v=adj[u][i].first, w=adj[u][i].second;
        if (v!=p)
        {
            par[v]={u, w};
            dfs(v, u, d+1, b);
        }
    }
}
void find_pair(int n, vector<int> u, vector<int> v, int a, int b)
{
    for (int i=0; i<=n-2; i++)
        vec.push_back(0);
    long long res=ask(vec)/a;
    int l=0, r=n-2, ans;
    while (l<r)
    {
        int mid=(l+r)/2;
        for (int i=0; i<=n-2; i++)
            vec[i]=0;
        for (int i=l; i<=mid; i++)
            vec[i]=1;
        if (ask(vec)==res*a)
            l=mid+1;
        else
            r=mid;
    }
    for (int i=0; i<=n-2; i++)
    {
        if (i!=l)
        {
            adj[u[i]].push_back({v[i], i});
            adj[v[i]].push_back({u[i], i});
        }
    }
    dfs(u[l], -1, 0, 1);
    dfs(v[l], -1, 0, 0);
    l=0, r=vu.size()-1;
    while (l<r)
    {
        int mid=(l+r+1)/2;
        for (int i=0; i<=n-2; i++)
            vec[i]=0;
        for (int i=mid; i<=r; i++)
            vec[par[vu[i]].second]=1;
        if (ask(vec)==res*a)
            r=mid-1;
        else
            l=mid;
    }
    ans=vu[l];
    l=0, r=vv.size()-1;
    while (l<r)
    {
        int mid=(l+r+1)/2;
        for (int i=0; i<=n-2; i++)
            vec[i]=0;
        for (int i=mid; i<=r; i++)
            vec[par[vv[i]].second]=1;
        if (ask(vec)==res*a)
            r=mid-1;
        else
            l=mid;
    }
    answer(ans, vv[l]);
}

Compilation message

highway.cpp: In function 'void dfs(int, int, int, bool)':
highway.cpp:13:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 |     for (int i=0; i<adj[u].size(); i++)
      |                   ~^~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2384 KB Output is correct
2 Correct 10 ms 3172 KB Output is correct
3 Correct 105 ms 8908 KB Output is correct
4 Correct 112 ms 8916 KB Output is correct
5 Correct 128 ms 8908 KB Output is correct
6 Correct 116 ms 8972 KB Output is correct
7 Correct 109 ms 9024 KB Output is correct
8 Correct 158 ms 8912 KB Output is correct
9 Correct 137 ms 8968 KB Output is correct
10 Correct 114 ms 8908 KB Output is correct
11 Correct 100 ms 9672 KB Output is correct
12 Correct 100 ms 10504 KB Output is correct
13 Correct 126 ms 10320 KB Output is correct
14 Correct 98 ms 10188 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 3656 KB Output is correct
2 Correct 20 ms 4936 KB Output is correct
3 Correct 41 ms 6340 KB Output is correct
4 Correct 95 ms 12708 KB Output is correct
5 Correct 85 ms 12728 KB Output is correct
6 Correct 135 ms 14204 KB Output is correct
7 Correct 119 ms 14844 KB Output is correct
8 Correct 97 ms 13272 KB Output is correct
9 Correct 91 ms 13420 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2440 KB Output is correct
2 Correct 11 ms 3024 KB Output is correct
3 Correct 72 ms 7696 KB Output is correct
4 Correct 145 ms 8952 KB Output is correct
5 Correct 91 ms 8908 KB Output is correct
6 Correct 105 ms 8900 KB Output is correct
7 Correct 136 ms 8904 KB Output is correct
8 Correct 173 ms 8900 KB Output is correct
9 Correct 123 ms 8980 KB Output is correct
10 Correct 100 ms 8908 KB Output is correct
11 Correct 108 ms 9808 KB Output is correct
12 Correct 101 ms 10820 KB Output is correct
13 Correct 106 ms 10448 KB Output is correct
14 Correct 109 ms 10032 KB Output is correct
15 Correct 124 ms 8920 KB Output is correct
16 Correct 125 ms 8908 KB Output is correct
17 Correct 106 ms 9912 KB Output is correct
18 Correct 148 ms 10508 KB Output is correct
19 Correct 138 ms 8980 KB Output is correct
20 Correct 143 ms 11028 KB Output is correct
21 Correct 95 ms 9160 KB Output is correct
22 Correct 125 ms 9272 KB Output is correct
23 Correct 139 ms 8996 KB Output is correct
24 Correct 141 ms 9444 KB Output is correct
25 Correct 135 ms 14240 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 2640 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 2672 KB Incorrect
2 Halted 0 ms 0 KB -