oj.uz

답안 #846674

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
846674 2023-09-08T08:50:52 Z vjudge1 Torrent (COI16_torrent) C++17
31 / 100
 349 ms 24036 KB 
#include<bits/stdc++.h>
using namespace std;

const int N = 3e5 + 5;

int n;
vector<int> adj[N];
vector<pair<int, int>> path;
int A, B, trace[N];

void dfs(int u, int p)
{
    for(auto v: adj[u])
    {
        if(v == p) continue;

        trace[v] = u;
        dfs(v, u);
    }
}

int DFS(int u, int p, pair<int, int> block) {
    int sum = 0;
    vector<int> res;

    for(int v : adj[u])
    {
        if(v == p)
            continue;

        if(make_pair(u, v) == block || make_pair(v, u) == block)
            continue;

        res.push_back(DFS(v, u, block));
    }

    sort(res.begin(), res.end());
    reverse(res.begin(), res.end());

    for(int i = 0; i < res.size(); i++)
        sum = max(sum, res[i] + (i + 1));

    return sum;
}

bool Check(int mid)
{
    //check coi max cay a > max cay b ko??
    pair<int, int> block = path[mid];

    return DFS(A, 0, block) > DFS(B, 0, block);

}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> A >> B;

    for(int i = 1; i < n; i ++)
    {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    dfs(A, 0);
    int x = B;
    while(x != A)
    {
        path.push_back({trace[x], x});
        x = trace[x];
    }

reverse(path.begin(), path.end());

//    for(auto tmp: path)
//    {
//        cout << tmp.first << ' ' << tmp.second << endl;
//    }

    int l = 0, r = path.size() - 1, ans = 0;
    while(l <= r)
    {
        int mid = (l + r) / 2;
        if(Check(mid))
        {
            ans = mid;
            r = mid - 1;
        }
        else
            l = mid + 1;
    }

    int res = max(DFS(A, 0, path[ans]), DFS(B, 0, path[ans]));
    res = min(res, max(DFS(A, 0, path[ans + 1]), DFS(B, 0, path[ans + 1])));
    cout << res;
}

Compilation message

torrent.cpp: In function 'int DFS(int, int, std::pair<int, int>)':
torrent.cpp:40:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |     for(int i = 0; i < res.size(); i++)
      |                    ~~^~~~~~~~~~~~

Subtask #1
31.0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 8536 KB Output is correct
2 Correct 2 ms 8536 KB Output is correct
3 Correct 3 ms 8540 KB Output is correct

Subtask #2
0 / 69.0

# 결과 실행 시간 메모리 Grader output
1 Correct 290 ms 20568 KB Output is correct
2 Correct 349 ms 21928 KB Output is correct
3 Correct 323 ms 23276 KB Output is correct
4 Correct 297 ms 22588 KB Output is correct
5 Correct 307 ms 19940 KB Output is correct
6 Correct 278 ms 20564 KB Output is correct
7 Incorrect 284 ms 24036 KB Output isn't correct
8 Halted 0 ms 0 KB -