oj.uz

답안 #701617

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
701617 2023-02-21T15:21:17 Z Do_you_copy Mag (COCI16_mag) C++17
120 / 120
 452 ms 211476 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
#define faster ios_base::sync_with_stdio(0); cin.tie(0);
#define pb push_back

using namespace std;
using ll = long long;
using pii = pair <int, int>;

const int maxN = 2e6 + 1;
const int inf = 0x3f3f3f3f;
//const int Mod =
int n;
int a[maxN];
vector <int> adj[maxN];
int dp[maxN][2];
struct TFrac{
    int x, y;
    bool operator < (const TFrac other) const{
        //x / y < other.x / other.y;
        //x * other.y < other.x * y;
        return x * other.y < other.x * y;
    }
};
TFrac ans = {1, 1};
void update(pair <pii, pii> &x, pii y){
    if (y > x.fi){
        swap(x.fi, x.se);
        x.fi = y;
    }
    else x.se = max(x.se, y);
}

void dfs(int u, int p){
    for (int i: adj[u]){
        if (i == p) continue;
        dfs(i, u);
    }
    if (a[u] > 2) return;
    if (a[u] == 1){
        pair <pii, pii> max1 = {{0, 0}, {0, 0}};
        pair <pii, pii> max2 = {{0, 0}, {0, 0}};
        for (int i: adj[u]){
            if (i == p) continue;
            update(max1, {dp[i][0], i});
            update(max2, {dp[i][1], i});
        }
        TFrac tem1 = {1, max1.fi.fi + max1.se.fi + 1};
        TFrac tem2;
        if (max1.fi.se == max2.fi.se){
            tem2.x = 2;
            tem2.y = 1 + max(max1.fi.fi + max2.se.fi, max1.se.fi + max2.fi.fi);
        }
        else{
            tem2.x = 2;
            tem2.y = 1 + max1.fi.fi + max2.fi.fi;
        }
        tem1 = min(tem1, tem2);
        ans = min(ans, tem1);
        dp[u][1] = 1 + max2.fi.fi;
        dp[u][0] = 1 + max1.fi.fi;
    }
    else{
        pii max1 = {0, 0};
        for (int i: adj[u]){
            if (i == p) continue;
            if (dp[i][0] > max1.fi){
                swap(max1.fi, max1.se);
                max1.fi = dp[i][0];
            }
            else max1.se = max(max1.se, dp[i][0]);
        }
        TFrac tem = {2, max1.fi + max1.se + 1};
        ans = min(ans, tem);
        dp[u][1] = 1 + max1.fi;
    }
    if (u == 1) cerr << dp[u][0] << ":D";
}
void Init(){
    cin >> n;
    for (int i = 1; i < n; ++i){
        int u, v;
        cin >> u >> v;
        adj[u].pb(v);
        adj[v].pb(u);
    }
    for (int i = 1; i <= n; ++i){
        cin >> a[i];
    }
    if (*min_element(a + 1, a + n + 1) > 1){
        cout << *min_element(a + 1, a + n + 1) << "/" << 1;
        return;
    }
    dfs(1, 0);
    int gcd = __gcd(ans.x, ans.y);
    ans.x /= gcd;
    ans.y /= gcd;
    cout << ans.x << "/" << ans.y;
}

#define taskname "test"
signed main(){
    faster
    if (fopen(taskname ".inp", "r")){
        freopen(taskname ".inp", "r", stdin);
        freopen(taskname ".out", "w", stdout);
    }
    int tt = 1;
    //cin >> tt;
    while (tt--){
        Init();
    }
    if (fopen("timeout.txt", "r")){
        ofstream timeout("timeout.txt");
        cerr << "Time elapsed: " << signed(double(clock()) / CLOCKS_PER_SEC * 1000) << "ms\n";
        timeout << signed(double(clock()) / CLOCKS_PER_SEC * 1000);
        timeout.close();
    }
}

Compilation message

mag.cpp: In function 'int main()':
mag.cpp:106:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  106 |         freopen(taskname ".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
mag.cpp:107:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  107 |         freopen(taskname ".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 27 ms 47316 KB Output is correct
2 Correct 25 ms 47348 KB Output is correct

Subtask #2
12.0 / 12.0

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

Subtask #3
12.0 / 12.0

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

Subtask #4
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 27 ms 47276 KB Output is correct
2 Correct 401 ms 204488 KB Output is correct

Subtask #5
12.0 / 12.0

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

Subtask #6
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 367 ms 91380 KB Output is correct
2 Correct 248 ms 80272 KB Output is correct

Subtask #7
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 317 ms 91216 KB Output is correct
2 Correct 76 ms 52888 KB Output is correct
3 Correct 452 ms 211476 KB Output is correct

Subtask #8
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 92 ms 51964 KB Output is correct
2 Correct 321 ms 92116 KB Output is correct
3 Correct 259 ms 70436 KB Output is correct

Subtask #9
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 292 ms 89408 KB Output is correct
2 Correct 300 ms 89444 KB Output is correct

Subtask #10
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 320 ms 91156 KB Output is correct
2 Correct 262 ms 70388 KB Output is correct