oj.uz

답안 #292271

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
292271 2020-09-06T17:03:31 Z SamAnd 통행료 (IOI18_highway) C++17
51 / 100
 299 ms 262148 KB 
#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
typedef long long ll;
const int N = 100005;

int n, m;
vector<int> g[N];
vector<int> gi[N];

int d[N];
int u[N];
void dfs0(int x, int p)
{
    if (x == p)
        d[x] = 0;
    for (int i = 0; i < g[x].size(); ++i)
    {
        int h = g[x][i];
        if (h == p)
        {
            u[x] = gi[x][i];
            continue;
        }
        d[h] = d[x] + 1;
        dfs0(h, x);
    }
}

void find_pair(int N_, std::vector<int> U, std::vector<int> V, int A, int B)
{
    n = N_;
    m = sz(U);
    for (int i = 0; i < m; ++i)
    {
        int x = U[i];
        int y = V[i];
        g[x].push_back(y);
        g[y].push_back(x);
        gi[x].push_back(i);
        gi[y].push_back(i);
    }

    vector<int> v;
    v.assign(m, 0);
    int dd = ask(v) / A;

    dfs0(0, 0);
    int maxu = 0;
    for (int x = 0; x < n; ++x)
        maxu = max(maxu, d[x]);
    int l = 1, r = maxu;
    int ans;
    while (l <= r)
    {
        int mid = (l + r) / 2;
        v.assign(m, 0);
        for (int x = 0; x < n; ++x)
        {
            if (d[x] >= mid)
            {
                v[u[x]] = 1;
            }
        }
        if (ask(v) != dd * 1LL * A)
        {
            ans = mid;
            l = mid + 1;
        }
        else
        {
            r = mid - 1;
        }
    }

    vector<int> t;
    for (int x = 0; x < n; ++x)
    {
        if (d[x] == ans)
        {
            t.push_back(x);
        }
    }
    int ans1;
    {
        int l = 0, r = sz(t) - 1;
        int ans;
        while (l <= r)
        {
            int mid = (l + r) / 2;
            v.assign(m, 0);
            for (int i = 0; i <= mid; ++i)
            {
                v[u[t[i]]] = 1;
            }
            if (ask(v) != dd * 1LL * A)
            {
                ans = t[mid];
                r = mid - 1;
            }
            else
                l = mid + 1;
        }
        ans1 = ans;
    }

    dfs0(ans1, ans1);
    t.clear();
    for (int x = 0; x < n; ++x)
    {
        if (d[x] == dd)
        {
            t.push_back(x);
        }
    }
    int ans2;
    {
        int l = 0, r = sz(t) - 1;
        int ans;
        while (l <= r)
        {
            int mid = (l + r) / 2;
            v.assign(m, 0);
            for (int i = 0; i <= mid; ++i)
            {
                v[u[t[i]]] = 1;
            }
            if (ask(v) != dd * 1LL * A)
            {
                ans = t[mid];
                r = mid - 1;
            }
            else
                l = mid + 1;
        }
        ans2 = ans;
    }
    answer(ans1, ans2);
}

Compilation message

highway.cpp: In function 'void dfs0(int, int)':
highway.cpp:22:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |     for (int i = 0; i < g[x].size(); ++i)
      |                     ~~^~~~~~~~~~~~~
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:143:11: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
  143 |     answer(ans1, ans2);
      |     ~~~~~~^~~~~~~~~~~~
highway.cpp:143:11: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
highway.cpp:84:9: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
   84 |         if (d[x] == ans)
      |         ^~

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 4992 KB Output is correct
2 Correct 4 ms 4992 KB Output is correct
3 Correct 4 ms 4992 KB Output is correct
4 Correct 4 ms 4992 KB Output is correct
5 Correct 4 ms 4992 KB Output is correct
6 Correct 4 ms 5084 KB Output is correct
7 Correct 4 ms 4992 KB Output is correct
8 Correct 3 ms 5084 KB Output is correct
9 Correct 4 ms 4992 KB Output is correct
10 Correct 5 ms 5024 KB Output is correct
11 Correct 4 ms 4992 KB Output is correct
12 Correct 4 ms 5080 KB Output is correct

Subtask #2
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 5160 KB Output is correct
2 Correct 18 ms 5888 KB Output is correct
3 Correct 206 ms 13616 KB Output is correct
4 Correct 181 ms 13488 KB Output is correct
5 Correct 185 ms 13584 KB Output is correct
6 Correct 190 ms 13524 KB Output is correct
7 Correct 195 ms 13572 KB Output is correct
8 Correct 193 ms 13512 KB Output is correct
9 Correct 192 ms 13544 KB Output is correct
10 Correct 195 ms 13492 KB Output is correct
11 Correct 211 ms 14620 KB Output is correct
12 Correct 207 ms 15296 KB Output is correct
13 Correct 211 ms 14740 KB Output is correct
14 Correct 200 ms 14708 KB Output is correct

Subtask #3
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 6656 KB Output is correct
2 Correct 32 ms 8088 KB Output is correct
3 Correct 42 ms 9592 KB Output is correct
4 Correct 130 ms 18820 KB Output is correct
5 Correct 157 ms 18928 KB Output is correct
6 Correct 132 ms 18808 KB Output is correct
7 Correct 126 ms 18808 KB Output is correct
8 Correct 124 ms 18844 KB Output is correct
9 Correct 170 ms 18812 KB Output is correct

Subtask #4
33.0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 5120 KB Output is correct
2 Correct 20 ms 6016 KB Output is correct
3 Correct 138 ms 11604 KB Output is correct
4 Correct 193 ms 13496 KB Output is correct
5 Correct 236 ms 13448 KB Output is correct
6 Correct 196 ms 13600 KB Output is correct
7 Correct 235 ms 13448 KB Output is correct
8 Correct 198 ms 13544 KB Output is correct
9 Correct 218 ms 13608 KB Output is correct
10 Correct 252 ms 13512 KB Output is correct
11 Correct 241 ms 14380 KB Output is correct
12 Correct 208 ms 15244 KB Output is correct
13 Correct 190 ms 14872 KB Output is correct
14 Correct 215 ms 15284 KB Output is correct
15 Correct 182 ms 13460 KB Output is correct
16 Correct 188 ms 13440 KB Output is correct
17 Correct 244 ms 14916 KB Output is correct
18 Correct 259 ms 14968 KB Output is correct
19 Correct 230 ms 13456 KB Output is correct
20 Correct 212 ms 15756 KB Output is correct
21 Correct 215 ms 14656 KB Output is correct
22 Correct 192 ms 14656 KB Output is correct
23 Correct 232 ms 14324 KB Output is correct
24 Correct 197 ms 14940 KB Output is correct
25 Correct 268 ms 18328 KB Output is correct

Subtask #5
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 299 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 276 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -