Submission #696163

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
696163	2023-02-05T17:01:02 Z	Nhoksocqt1	Mag (COCI16_mag)	C++17	120 / 120	1210 ms	229128 KB

#include<bits/stdc++.h>
using namespace std;

#define inf 0x3f3f3f3f
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#define fi first
#define se second
typedef long long ll;
typedef pair<int, int> ii;

template<class X, class Y>
	inline bool maximize(X &x, const Y &y) {return (x < y ? x = y, 1 : 0);}
template<class X, class Y>
	inline bool minimize(X &x, const Y &y) {return (x > y ? x = y, 1 : 0);}

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int Random(int l, int r) {
    return uniform_int_distribution<int>(l, r)(rng);
}

const int MAXN = 1000006;

set<int> G[MAXN];
int val[MAXN], sz[MAXN], numNode;

int dfsSize(int u, int p) {
    sz[u] = 1;
    for (int v : G[u]) {
        if(v != p)
            sz[u] += dfsSize(v, u);
    }

    return sz[u];
}

int centroid(int u, int p, int nSize) {
    for (int v : G[u]) {
        if(v != p && sz[v] > nSize / 2)
            return centroid(v, u, nSize);
    }

    return u;
}

ll p, q, pmin, qmin;
void dfs(int u, int pa, int c, ll pn, ll qn, ll &pnow, ll &qnow) {
    if(double(1e15) / pn >= val[c] && double(p) / q > double(pn) * val[c] / (qn + 1))
        p = pn * val[c], q = qn + 1;

    if(double(1e15) / (pn) >= pmin && double(pn) * pmin / (qn + qmin) < double(p) / q)
        p = pn * pmin, q = qn + qmin;

    if(double(1e15) / pn >= val[c] && double(pnow) / qnow > double(pn) * val[c] / (qn + 1))
        pnow = pn * val[c], qnow = qn + 1;

    for (int v : G[u]) {
        if(v != pa && double(1e15) / pn >= val[v])
            dfs(v, u, c, pn * val[v], qn + 1, pnow, qnow);
    }
}

void build(int u, int p) {
    int nSize = dfsSize(u, p);
    int c = centroid(u, p, nSize);

    pmin = 1e18, qmin = 1;
    for (int v : G[c]) {
        ll pnow(1e18), qnow(1);
        dfs(v, c, c, val[v], 1, pnow, qnow);

        if(double(pnow) / qnow < double(pmin) / qmin)
            pmin = pnow, qmin = qnow;
    }

    vector<int> tmp(G[c].begin(), G[c].end());
    for (int it = 0; it < int(tmp.size()); ++it) {
        int v(tmp[it]);
        G[c].erase(v);
        G[v].erase(c);
        build(v, c);
    }
}

void process() {
    cin >> numNode;
    for (int i = 1; i < numNode; ++i) {
        int u, v;
        cin >> u >> v;
        G[u].insert(v);
        G[v].insert(u);
    }

    p = 1e18, q = 1;
    for (int i = 1; i <= numNode; ++i) {
        cin >> val[i];
        p = min(p, 1LL * val[i]);
    }

    build(1, 0);

    ll gcd = __gcd(p, q);
    p /= gcd, q /= gcd;
    cout << p << '/' << q;
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

//    freopen("mag.inp", "r", stdin);
//    freopen("mag.out", "w", stdout);

    process();
    return 0;
}

Compilation message

mag.cpp:6: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    6 | #pragma GCC optimization ("O3")
      | 
mag.cpp:7: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    7 | #pragma GCC optimization ("unroll-loops")
      |

Subtask #1
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	20 ms	47316 KB	Output is correct
2	Correct	21 ms	47312 KB	Output is correct

Subtask #2
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	21 ms	47288 KB	Output is correct
2	Correct	22 ms	47336 KB	Output is correct

Subtask #3
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	968 ms	186412 KB	Output is correct

Subtask #4
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	20 ms	47316 KB	Output is correct
2	Correct	923 ms	225664 KB	Output is correct

Subtask #5
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1210 ms	224564 KB	Output is correct

Subtask #6
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	678 ms	163676 KB	Output is correct
2	Correct	699 ms	132860 KB	Output is correct

Subtask #7
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	581 ms	166536 KB	Output is correct
2	Correct	177 ms	59108 KB	Output is correct
3	Correct	1084 ms	229128 KB	Output is correct

Subtask #8
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	222 ms	58824 KB	Output is correct
2	Correct	790 ms	164500 KB	Output is correct
3	Correct	1070 ms	105860 KB	Output is correct

Subtask #9
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	597 ms	156668 KB	Output is correct
2	Correct	579 ms	164132 KB	Output is correct

Subtask #10
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	999 ms	164848 KB	Output is correct
2	Correct	1114 ms	105828 KB	Output is correct