oj.uz

답안 #162894

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
162894 2019-11-10T08:39:17 Z _qVp_ Mag (COCI16_mag) C++14
96 / 120
 611 ms 155000 KB 
#include <bits/stdc++.h>
    
using namespace std;
    
const int md = 1e6 + 10;
typedef pair < long long, int > II;    

vector < int > adj[md];
int a[md], u[md], v[md], par[md];
int f[md][5];
queue < int > q;
int n;
long long a1 = 1e9, b1 = 1;
    
void compare(long long a2, long long b2) {
    if (a1 * b2 >= a2 * b1) {
        a1 = a2;
        b1 = b2;
    }
}

void dfs(int u, int root) {
    for(int i = 0; i < adj[u].size(); i++) {
        int v = adj[u][i];
        if (par[u] == v) continue;
        par[v] = u;
        dfs(v, root);
    }
    //cout << u << "*\n";
    int smax1 = 0, fmax1 = 0, smax2 = 0, pmax1 = 0, pmax2 = 0;
    for(int i = 0; i < adj[u].size(); i++) {
        int v = adj[u][i];
        if (par[u] == v) continue;
        if (fmax1 < f[v][0]) {
            pmax1 = v;
            fmax1 = f[v][0];
        }
        if (smax2 < f[v][1]) {
            smax2 = f[v][1];
            pmax2 = v;
        }
    //    cout << "(" << f[v][0] << " " << f[v][1] << ") ";
    }
    //cout << endl;
    for(int i = 0; i < adj[u].size(); i++) {
        int v = adj[u][i];
        if (par[u] == v || v == pmax1) continue;
        smax1 = max(smax1, f[v][0]);
    }
    //cout << fmax1 << " " << smax1 << " " << smax2 << endl; 
    if (a[u] == 1) {
        compare(1, 1);
        compare(1, smax1 + fmax1 + 1);
        if (pmax1 != pmax2)
            compare(2, fmax1 + smax2 + 1);
        compare(1, fmax1 + 1);
        compare(2, smax2 + 1);
        if (fmax1 > 0)
            f[u][0] = fmax1 + 1;
        if (smax2 > 0)
            f[u][1] = smax2 + 1;
    } else {
        compare(2, 1);
        compare(2, smax1 + fmax1 + 1);
        if (fmax1 > 0)
            f[u][1] = fmax1 + 1;
    }
    //if (a1 == 2 && b1 == 9)
    //    cout << "false\n";
    //cout << f[u][0] << " " << f[u][1] << endl;
}

int main() {
    //freopen("test.in", "r", stdin);
    //freopen("test.out", "w", stdout);
    ios_base::sync_with_stdio(0);
    cin >> n;
    for(int i = 1; i < n; i++) 
        cin >> u[i] >> v[i];
    for(int i = 1; i <= n; i++)
        cin >> a[i];
    for(int i = 1; i < n; i++) {
        //int u, v;
        //cin >> u >> v;
        if (a[u[i]] + a[v[i]] <= 3) {
            adj[u[i]].push_back(v[i]);
            adj[v[i]].push_back(u[i]);

        }
    }
    for(int i = 1; i <= n; i++) {
        f[i][0] = (a[i] == 1);
        f[i][1] = (a[i] == 2);
    }
    for(int i = 1; i <= n; i++) 
        if (!par[i]) {
            if (a[i] >= 3) {
                compare(a[i], 1);
                continue;
            }
            //cout << i << endl;
            par[i] = i;
            dfs(i, i);
        }
    //for(int i = 1; i <= n; i++)
    //    cout << i <<" " << f[i][0] << " " << f[i][1] << endl;
    cout << a1 << "/" << b1;
    return 0;
}

Compilation message

mag.cpp: In function 'void dfs(int, int)':
mag.cpp:23:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < adj[u].size(); i++) {
                    ~~^~~~~~~~~~~~~~~
mag.cpp:31:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < adj[u].size(); i++) {
                    ~~^~~~~~~~~~~~~~~
mag.cpp:45:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < adj[u].size(); i++) {
                    ~~^~~~~~~~~~~~~~~

Subtask #1
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 23928 KB Output is correct
2 Correct 24 ms 23932 KB Output is correct

Subtask #2
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 34 ms 23928 KB Output is correct
2 Incorrect 25 ms 24160 KB Output isn't correct

Subtask #3
12.0 / 12.0

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

Subtask #4
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 23804 KB Output is correct
2 Correct 483 ms 101388 KB Output is correct

Subtask #5
12.0 / 12.0

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

Subtask #6
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 502 ms 105280 KB Output is correct
2 Correct 379 ms 83708 KB Output is correct

Subtask #7
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 498 ms 108220 KB Output is correct
2 Correct 99 ms 32248 KB Output is correct
3 Correct 554 ms 155000 KB Output is correct

Subtask #8
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 91 ms 31992 KB Output is correct
2 Correct 505 ms 105456 KB Output is correct
3 Correct 401 ms 65352 KB Output is correct

Subtask #9
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 471 ms 100580 KB Output is correct
2 Correct 503 ms 102136 KB Output is correct

Subtask #10
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 611 ms 106112 KB Output isn't correct
2 Halted 0 ms 0 KB -