oj.uz

답안 #25899

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
25899 2017-06-25T03:16:12 Z model_code Triumphal arch (POI13_luk) C++11
100 / 100
 1543 ms 25744 KB 
/*************************************************************************
 *                                                                       *
 *                    XX Olimpiada Informatyczna                         *
 *                                                                       *
 *   Zadanie:              Luk triumfalny                                *
 *   Autor:                Wiktor Kuropatwa                              *
 *   Zlozonosc czasowa:    O(n log n)                                    *
 *   Zlozonosc pamieciowa: O(n)                                          *
 *   Opis:                 Rozwiazanie wzorcowe                          *
 *                                                                       *
 *************************************************************************/

#include <cstdio>
#include <algorithm>
#include <vector>

using namespace std;

vector<int> D[300005];
int add[300005];
int n,ignore;

void read()
{
    ignore = scanf("%d", &n);
    for(int i = 1; i<n; i++)
    {
        int a,b;
        ignore = scanf("%d%d", &a, &b);
        D[a].push_back(b);
        D[b].push_back(a);
    }
}
void root(int u, int p)
{
    for(int i = 0; i<(int)D[u].size(); i++)
    {
        if(D[u][i] != p)
            root(D[u][i],u);
        else
        {
            swap(D[u][i], D[u].back());
            D[u].pop_back();
            i--;
        }
    }
}
void dfs(int u, int s)
{
    if(D[u].size() == 0)
    {
        add[u] = 0;
        return;
    }
    for(int i = 0; i<(int)D[u].size(); i++)
        dfs(D[u][i],s);
    add[u] = 0;
    for(int i = 0; i<(int)D[u].size(); i++)
        add[u] += add[D[u][i]] + 1;
    add[u] -= s;
    add[u] = max(add[u],0);
}
bool check(int s)
{
    dfs(1,s);
    return !add[1];
}
int binSearch()
{
    int p = 0, q = n;
    while(q-p>1)
    {
        int s = (p+q)/2;
        if(check(s))
            q = s;
        else
            p = s;
    }
    if(check(p))
        return p;
    return q;
}
int main()
{
    read();
    root(1,1);
    printf("%d\n", binSearch());
    return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 39 ms 10432 KB Output is correct
2 Correct 49 ms 11332 KB Output is correct
3 Correct 26 ms 10564 KB Output is correct

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 256 ms 12676 KB Output is correct
2 Correct 333 ms 14912 KB Output is correct
3 Correct 96 ms 13076 KB Output is correct

Subtask #8
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 413 ms 15976 KB Output is correct
2 Correct 889 ms 21652 KB Output is correct
3 Correct 239 ms 16784 KB Output is correct

Subtask #9
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 829 ms 19276 KB Output is correct

Subtask #10
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1223 ms 19276 KB Output is correct
2 Correct 1543 ms 25744 KB Output is correct
3 Correct 379 ms 20312 KB Output is correct