oj.uz

Submission #923584

# Submission time Handle Problem Language Result Execution time Memory
923584 2024-02-07T12:42:28 Z codefox Torrent (COI16_torrent) C++14
100 / 100
 663 ms 32596 KB 
#include <bits/stdc++.h>

using namespace std;


vector<vector<int>> graph;
vector<int> opt;
vector<int> path;
int f, s;
bool pos = 1;
int border = -1;
int sol = 0;

void dfs(int i, int p, int limit)
{
    opt[i] = 0;
    vector<int> subs;
    int alt = -1;
    for (int ele:graph[i])
    {
        if (ele==p) continue;
        if (!path[ele]) 
        {
            dfs(ele, i, limit);
            subs.push_back(opt[ele]);
        }
        else alt = ele;
    }
    sort(subs.begin(), subs.end(), greater<int>());
    int newl = limit-1;
    for (int j = 0; j < subs.size(); j++)
    {
        if (subs[j]+j+1==limit) newl = subs[j]-1;
        opt[i] = max(opt[i], subs[j]+j+1);
    }
    if (opt[i]>limit)
    {
        if (path[i]) border = p;
        if (opt[i]>sol) pos = 0;
    }
    else 
    {
        if (alt==s) border = i;
        else if (alt != -1) dfs(alt, i, newl);
    }
}

void check(int i, int p)
{
    opt[i] = 0;
    vector<int> subs;
    for (int ele:graph[i])
    {
        if (ele == p) continue;
        if (ele == border) continue;
        check(ele, i);
        subs.push_back(opt[ele]);
    }
    sort(subs.begin(), subs.end(), greater<int>());
    for (int j = 0; j < subs.size(); j++)
    {
        opt[i] = max(opt[i], subs[j]+j+1);
    }
    if (opt[i]>sol) pos = 0;
}

int findpath(int i, int p)
{
    if (i==f) return 1;
    for (int ele:graph[i])
    {
        if (ele==p) continue;
        if (findpath(ele, i)) path[i] = 1;
    }
    return path[i];
}


int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);

    int n;
    cin >> n >> f >> s;
    f--; s--;
   
    graph = vector<vector<int>>(n);
    path = vector<int>(n, 0);
    opt = vector<int>(n, 0);

    for (int i = 1; i < n; i++)
    {
        int a, b;
        cin >> a >> b;
        a--; b--;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    findpath(s, -1);

    for (int i = 29; i >= 0; i--)
    {
        pos = 1;
        border = f;

        sol += 1<<i;

        dfs(f, -1, sol);
        check(s, -1);

        if (pos) sol -= 1<<i;
    }
    cout << sol+1;

    return 0;
}

Compilation message

torrent.cpp: In function 'void dfs(int, int, int)':
torrent.cpp:31:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |     for (int j = 0; j < subs.size(); j++)
      |                     ~~^~~~~~~~~~~~~
torrent.cpp: In function 'void check(int, int)':
torrent.cpp:60:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |     for (int j = 0; j < subs.size(); j++)
      |                     ~~^~~~~~~~~~~~~

Subtask #1
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct

Subtask #2
69.0 / 69.0

# Verdict Execution time Memory Grader output
1 Correct 552 ms 23364 KB Output is correct
2 Correct 663 ms 30392 KB Output is correct
3 Correct 456 ms 31944 KB Output is correct
4 Correct 513 ms 31960 KB Output is correct
5 Correct 550 ms 26856 KB Output is correct
6 Correct 501 ms 27300 KB Output is correct
7 Correct 413 ms 32596 KB Output is correct