oj.uz

답안 #27170

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
27170 2017-07-09T18:37:54 Z Bruteforceman Torrent (COI16_torrent) C++11
100 / 100
 1263 ms 30144 KB 
#include <bits/stdc++.h>
using namespace std;
vector <int> g[300010];
int u[300010], v[300010];
int vis;

int dp(int x, int par) {
   // cout << x << " " << par << endl;
    vector <int> a;
    for(auto e : g[x]) {
        int i = u[e] ^ v[e] ^ x;
        if(e == vis) continue;
        if(i == par) continue;
        a.push_back(dp(i, x));
    } 
    sort(a.begin(), a.end());
    reverse(a.begin(), a.end());
    int ans = 0;
    for(unsigned i = 0; i < a.size(); i++) {
        ans = max(ans, a[i] + int(i + 1));
    }
    return ans;
}

int pa[300010];
int d[300010];
const int inf = 1e9;

void dfs(int x, int par) {
    for(auto e : g[x]) {
        int i = u[e] ^ v[e] ^ x;
        if(i == par) continue;
        d[i] = 1 + d[x];
        pa[i] = e;
        dfs(i, x);
    }
}

int a, b;
pair <int, int> func(int up) { 
    int cur = b;
    while(up > 1) {
        --up;
        int e = pa[cur];
        cur ^= u[e] ^ v[e];
    }
    vis = pa[cur];
    return make_pair(dp(a, 0), dp(b, 0));
}
int search(int b, int e) {
    if(b == e) {
        pair <int, int> p = func(b);
        return max(p.first, p.second);
    }
    if(e - b == 1) {
        return min(search(b, b), search(e, e));
    }
    int m = (b + e) >> 1;
    pair <int, int> p = func(m);
    if(p.first - p.second >= 0) return search(m, e);
    else return search(b, m - 1);
} 

int find(int b, int e) {
    if(b == e) {
        pair <int, int> p = func(b);
        return max(p.first, p.second);
    }
    if(e - b == 1) {
        return min(find(b, b), find(e, e));
    }
    int m = (b + e) >> 1;
    pair <int, int> p = func(m);
    if(p.first - p.second <= 0) return find(m, e);
    else return find(b, m - 1); 
}

int main() {
    int n;
    scanf("%d %d %d", &n, &a, &b);
    for(int i = 1; i < n; i++) {
        int p, q;
        scanf("%d %d", &p, &q);
        g[p].push_back(i);
        g[q].push_back(i);
        u[i] = p;
        v[i] = q;
    }
    dfs(a, 0);
/*
    vector <int> vec;
    for(int i = 1; i <= d[b]; i++) {
        ans = min(ans, func(i));
        vec.push_back(junk(i));
    }
    reverse(vec.begin(), vec.end());
    assert(is_sorted(vec.begin(), vec.end()));
*/
    int p = search(1, d[b]);
    int q = find(1, d[b]);
    printf("%d\n", min(p, q));
    return 0;
}

Compilation message

torrent.cpp: In function 'int main()':
torrent.cpp:80:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d", &n, &a, &b);
                                  ^
torrent.cpp:83:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &p, &q);
                               ^

Subtask #1
31.0 / 31.0

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

Subtask #2
69.0 / 69.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1166 ms 25432 KB Output is correct
2 Correct 1263 ms 26812 KB Output is correct
3 Correct 1126 ms 28928 KB Output is correct
4 Correct 1143 ms 27484 KB Output is correct
5 Correct 1143 ms 25024 KB Output is correct
6 Correct 1069 ms 25908 KB Output is correct
7 Correct 963 ms 30144 KB Output is correct