oj.uz

Submission #887936

# Submission time Handle Problem Language Result Execution time Memory
887936 2023-12-15T14:23:24 Z Yang8on Mag (COCI16_mag) C++14
120 / 120
 331 ms 154736 KB 
#include <bits/stdc++.h>

#define Yang8on Nguyen_Dinh_Son
#define sonphamay Nguyen_Dinh_Son

#define aothtday "Mag"
#define fi(i, a, b) for(int i = a; i <= b; i++)
#define fid(i, a, b) for(int i = a; i >= b; i--)
#define ll long long
#define endl '\n'
#define pii pair<int, ll>
#define vi vector<int>
#define pb push_back
#define all(v) v.begin(), v.end()
#define F first
#define S second
#define maxn 1000005
#define maxm
#define maxx
#define mod 1000000007
#define base 311
#define ModHas 1000000003ll
#define gb(i, j) ((i >> j) & 1)

using namespace std;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

ll GetRandom(ll l, ll r)
{
    return uniform_int_distribution<ll> (l, r)(rng);
}

/// lg, alg: longest, almost longest (*NOTE)

int n;
int a[maxn];
vector<int> o[maxn];

int dp[maxn][3]; /// dp[u][0/1]: (longest, almost longest) node 1, from child to u
void dfs(int u, int par) /// dfs down
{
    for(int v : o[u])
    {
        if(v == par) continue;
        dfs(v, u);

        if(a[v] == 1)
        {
            if(dp[u][0] < dp[v][0] + 1)
            {
                dp[u][1] = dp[u][0];
                dp[u][0] = dp[v][0] + 1;
            }
            else if(dp[u][1] < dp[v][0] + 1)
            {
                dp[u][1] = dp[v][0] + 1;
            }
        }
    }
}

int dp2[maxn]; /// dp2[u] : longest node 1, from root to u
void dfs2(int u, int par) /// dfs up
{
    for(int v : o[u])
    {
        if(v == par) continue;

        if(a[u] == 1)
        {
            dp2[v] = max(dp2[v], dp2[u] + 1);
            if(dp[u][0] == dp[u][1]) dp2[v] = max(dp2[v], dp[u][0] + 1); /// if lg, alg equal to each other --> no matter v belong lg or alg
            else if(dp[v][0] + 1 != dp[u][0]) dp2[v] = max(dp2[v], dp[u][0] + 1); /// v not belong lg --> using lg
            else if(dp[v][0] + 1 == dp[u][1]) dp2[v] = max(dp2[v], dp[u][1] + 1); /// v belong lg --> using alg
        }

        dfs2(v, u);
    }
}

void solve()
{
    cin >> n;
    fi(i, 1, n - 1)
    {
        int x, y;
        cin >> x >> y;
        o[x].pb(y);
        o[y].pb(x);
    }

    fi(i, 1, n) cin >> a[i];

    dfs(1, 0); /// dfs down
    dfs2(1, 0); /// dfs up

    ll P = -1, Q = -1;
    fi(i, 1, n)
    {
        /// the optimal solution for i is a[i] / (m + 1) , which mean (1 * 1 * ... * 1 * a[i]) / 1 + 1 + 1 + .. + 1

        int m1 = dp2[i], m2 = dp[i][0], m3 = dp[i][1];
        int m = max({m1 + m2, m1 + m3, m2 + m3});

        if(P == -1) P = a[i], Q = m + 1;
        else if(1ll * P * (m + 1) > 1ll * Q * a[i]) P = a[i], Q = m + 1;
    }

    ll G = __gcd(P, Q);

    cout << P / G << "/" << Q / G;
}

/*
5
1 2
2 3
1 4
4 5
2 1 1 1 1
*/
int main()
{
    if(fopen(aothtday".inp", "r"))
    {
        freopen(aothtday".inp","r",stdin);
        freopen(aothtday".out","w",stdout);
    }

    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);

    int nTest = 1;
//    cin >> nTest;

    while(nTest --)
    {
        solve();
    }

    return 0;
}

Compilation message

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

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 24924 KB Output is correct
2 Correct 6 ms 24924 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 24924 KB Output is correct
2 Correct 5 ms 25100 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 244 ms 104460 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 24924 KB Output is correct
2 Correct 326 ms 151884 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 320 ms 151640 KB Output is correct

Subtask #6
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 247 ms 89768 KB Output is correct
2 Correct 186 ms 73304 KB Output is correct

Subtask #7
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 244 ms 92792 KB Output is correct
2 Correct 39 ms 33284 KB Output is correct
3 Correct 331 ms 154736 KB Output is correct

Subtask #8
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 33108 KB Output is correct
2 Correct 247 ms 90140 KB Output is correct
3 Correct 201 ms 58740 KB Output is correct

Subtask #9
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 233 ms 88012 KB Output is correct
2 Correct 261 ms 90988 KB Output is correct

Subtask #10
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 269 ms 90476 KB Output is correct
2 Correct 212 ms 58968 KB Output is correct