oj.uz

답안 #846657

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
846657 2023-09-08T08:26:24 Z vjudge1 Torrent (COI16_torrent) C++17
100 / 100
 313 ms 26872 KB 
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define eb emplace_back
#define task "Torrent"
#define fast ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define nx freopen (task".inp","r",stdin), freopen (task".out","w",stdout);
#define fi first
#define se second
#define pii pair <int, int>
#define tii tuple <int, int, int>
using namespace std;
const int nmax = 300002;
int n, a, b, par[nmax];
vector <int> adj[nmax], Path;
int dp[nmax][2], ans = 1e9;
//0 a, 1 b
bool vs[nmax];
void get_path(int u)
{ 
    for (auto &v : adj[u])
    {
        if (v == par[u]) continue;
        par[v] = u;
        get_path(v);
    }
}
void solve(int u, int p, int type)
{
    dp[u][type] = 0;
    vector <int> best;
    for (auto &v : adj[u])
    {
        if (v == p || vs[v]) continue;
        solve(v, u, type);
        best.eb(dp[v][type]);
    }
    sort(best.rbegin(), best.rend());
    for (int i = 0; i < best.size(); ++i)
        dp[u][type] = max(dp[u][type], best[i] + i + 1);
}
bool check(int u, int v)
{
    vs[v] = 1, solve(a, a, 0), vs[v] = 0;
    vs[u] = 1, solve(b, b, 1), vs[u] = 0;
    ans = min(ans, max(dp[a][0], dp[b][1]));
    return dp[a][0] < dp[b][1];
}
int main()
{
    if (ifstream(task".inp")) nx
    fast
    cin >> n >> a >> b;
    for (int u, v, i = 1; i < n; ++i)
    {
        cin >> u >> v;
        adj[u].eb(v);
        adj[v].eb(u);
    }
    get_path(a);
    int x = b;
    while(x != a)
    {
        Path.eb(x);
        x = par[x];
    }
    Path.eb(a);
    reverse(Path.begin(), Path.end());
    int l = 0, r = Path.size() - 2;
    while (l <= r)
    {
        int mid = l + r >> 1;
        if (check(Path[mid], Path[mid + 1]))
            l = mid + 1;
        else r = mid - 1;
    }
    cout << ans;
}

Compilation message

torrent.cpp: In function 'void solve(int, int, int)':
torrent.cpp:39:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |     for (int i = 0; i < best.size(); ++i)
      |                     ~~^~~~~~~~~~~~~
torrent.cpp: In function 'int main()':
torrent.cpp:72:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   72 |         int mid = l + r >> 1;
      |                   ~~^~~
torrent.cpp:7:20: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    7 | #define nx freopen (task".inp","r",stdin), freopen (task".out","w",stdout);
      |            ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
torrent.cpp:51:31: note: in expansion of macro 'nx'
   51 |     if (ifstream(task".inp")) nx
      |                               ^~
torrent.cpp:7:52: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    7 | #define nx freopen (task".inp","r",stdin), freopen (task".out","w",stdout);
      |                                            ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
torrent.cpp:51:31: note: in expansion of macro 'nx'
   51 |     if (ifstream(task".inp")) nx
      |                               ^~

Subtask #1
31.0 / 31.0

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

Subtask #2
69.0 / 69.0

# 결과 실행 시간 메모리 Grader output
1 Correct 280 ms 23112 KB Output is correct
2 Correct 313 ms 24704 KB Output is correct
3 Correct 309 ms 26364 KB Output is correct
4 Correct 281 ms 26036 KB Output is correct
5 Correct 268 ms 22352 KB Output is correct
6 Correct 245 ms 23216 KB Output is correct
7 Correct 270 ms 26872 KB Output is correct