Submission #701617

#	Time	Username	Problem	Language	Result	Execution time	Memory
701617		Do_you_copy	Mag (COCI16_mag)	C++17	120 / 120	452 ms	211476 KiB

mag

#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 (stderr)

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 / 12
• Subtask 2: 12 / 12
• Subtask 3: 12 / 12
• Subtask 4: 12 / 12
• Subtask 5: 12 / 12
• Subtask 6: 12 / 12
• Subtask 7: 12 / 12
• Subtask 8: 12 / 12
• Subtask 9: 12 / 12
• Subtask 10: 12 / 12