Submission #1221065

#	Time	Username	Problem	Language	Result	Execution time	Memory
1221065		sunflower	Mag (COCI16_mag)	C++17	120 / 120	266 ms	145012 KiB

mag

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

#define ll long long
#define MASK(x) (1LL << (x))
#define BIT(x, i) (((x) >> (i)) & 1)
#define SZ(x) ((int) (x).size())
#define ALL(a) (a).begin(), (a).end()
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define FORD(i, a, b) for (int i = (a), _b = (b); i >= _b; --i)
#define REP(i, n) for (int i = 0; i < (n); ++i)

#define F first
#define S second
#define left    __left
#define right   __right
#define prev    __prev
#define next    __next

template <class X, class Y>
    bool maximize(X &x, Y y) {
        if (x < y) return x = y, true;
        else return false;
    }

template <class X, class Y>
    bool minimize(X &x, Y y) {
        if (x > y) return x = y, true;
        else return false;
    }

template <class T>
    void get_min(T &x, T y) {
        if (1LL * x.F * y.S > 1LL * y.F * x.S) x = y;
    }

#define MAX_NODE 1'000'100
int numNode;

int magic[MAX_NODE + 2];
vector<int> adj[MAX_NODE + 2];

namespace subtask1 {
    bool check() {
        return (numNode <= 1000);
    }

    const long long INF = (long long) 1e18 + 7;

    long long cost[1010];
    int high[1010];

    void dfs(int u, int par = -1) {
        for (int v : adj[u]) {
            if (v == par) continue;

            high[v] = high[u] + 1;
            if (cost[u] <= INF / magic[v]) {
                cost[v] = cost[u] * magic[v];
            } else {
                cost[v] = INF;
            }
            dfs(v, u);
        }
    }


    void solve() {
        int minMagic = *min_element(magic + 1, magic + 1 + numNode);

        /// max P (chua chia Q) <= 1e9 * 1e6 = 1e15;

        pair <long long, int> res = {minMagic, 1};

        FOR(u, 1, numNode - 1) {
            cost[u] = magic[u];
            high[u] = 1;
            dfs(u);

            FOR(v, u + 1, numNode) {
                if (cost[v] == INF) continue;
                ll x = __gcd(cost[v], 1LL * high[v]);
                pair <long long, int> tmp = {cost[v] / x, high[v] / x};
                get_min(res, tmp);
            }
        }

        cout << res.F << "/" << res.S;
    }
};
/// can prove:
/// optimal path: K nodes = 1 or 2 * K nodes (x so 1 -- 2 -- x so 1)
/**
    A * B / (x + y + z + 1) < A / x (ko the xay ra); /// A, B > 1;
    1 / x > A / (x + y + 1) (x >= y); // (best choice is x = y and A = 2);
**/


namespace subtaskFull {
    pair <int, int> one[MAX_NODE + 2];
    pair <int, int> res;

    void update(pair <int, int> &ans, int val) {
        if (val > ans.F) {
            ans.S = ans.F;
            ans.F = val;
        } else {
            maximize(ans.S, val);
        }
    }

    void dfs(int u, int par = -1) {
        for (int v : adj[u]) {
            if (v == par) continue;
            dfs(v, u);

            if (magic[v] == 1) {
                update(one[u], one[v].F + 1);
            }
        }
    }

    void modify(int v, int u) {
        if (magic[u] != 1) return;

        if (magic[v] == 1 && magic[v] + one[v].F == one[u].F) update(one[v], one[u].S + 1);
        else update(one[v], one[u].F + 1);
    }

    void reroot(int u, int par = -1) {
        if (magic[u] <= 2) {
            pair <int, int> tmp = make_pair(magic[u], one[u].F + one[u].S + 1);
            int x = __gcd(tmp.F, tmp.S);
            tmp.F /= x;
            tmp.S /= x;

//            cout << "u = " << u << " --> " << one[u].F << " " << one[u].S << endl;
            get_min(res, tmp);
        }

        for (int v : adj[u]) {
            if (v == par) continue;

            modify(v, u);
            reroot(v, u);
///           modify(u, v);

        }
    }

    void solve() {
        FOR(u, 1, numNode) one[u] = {0, 0};
        res = {1, 1}; /// minmagic = 1;

        /// with each node, find 2 path max len with all magic = 1;
        dfs(1);

        reroot(1);

        cout << res.F << "/" << res.S;
    }
};

int main() {
    ios_base::sync_with_stdio(false);cin.tie(nullptr);
    if (fopen("test.inp","r")) {
        freopen("test.inp","r",stdin);
        freopen("test.out","w",stdout);
    }
    cin >> numNode;
    REP(i, numNode - 1) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    FOR(i, 1, numNode) cin >> magic[i];

    int minMagic = *min_element(magic + 1, magic + 1 + numNode);
    if (minMagic > 1) { /// easy to prove;
        cout << minMagic << "/" << 1;
        return 0;
    }
    /// all rem number > 1 ==> them so cx chi lam tang value;

//    if (subtask1 :: check()) return subtask1 :: solve(), 0;
    subtaskFull :: solve();

    return 0;
}

Compilation message (stderr)

mag.cpp: In function 'int main()':
mag.cpp:167:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  167 |         freopen("test.inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
mag.cpp:168:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  168 |         freopen("test.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