Submission #736148

#	Time	Username	Problem	Language	Result	Execution time	Memory
736148		marvinthang	Putovanje (COCI20_putovanje)	C++17	110 / 110	202 ms	24928 KiB

putovanje

/******************************
*    author : @marvinthang    *
*    date : 14 / 11 / 2021    *
******************************/

#include <bits/stdc++.h>

using namespace std;

#define  superspeed  ios_base::sync_with_stdio(false);\
                     cin.tie(NULL);\
                     //cout.tie(NULL);
#define  file(name)  freopen(name".inp", "r", stdin);\
                     freopen(name".out", "w", stdout);

const       int MOD = 1e9 + 7; // 998244353;
const     double PI = 3.1415926535897932384626433832795; // acos((db)-1); atan(-1.0);
const      int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
const  long long oo = 1e18;
const       int MAX = 2e5 + 5;
const       int LOG = 18;

struct EDGE {
    int u, v, cost1, costfull;
    bool operator < (const EDGE &a) const {
        return u == a.u ? v < a.v : u < a.u;
    }
};

int numNode;
EDGE edges[MAX];
vector <int> adj[MAX];
int par[MAX], pref[MAX], anc[MAX][LOG], depth[MAX];

int findEdge(int u, int v) {
    if (u > v) swap(u, v);
    EDGE tmp = {u, v, 0, 0};
    int l = 1, r = numNode - 1, res = -1;
    while (l <= r) {
        int mid = (l + r) / 2;
        if (edges[mid].u == u && edges[mid].v == v) return mid;
        if (edges[mid] < tmp) l = mid + 1;
        else r = mid - 1;
    }
    return res;
}

void dfs(int u) {
    depth[u] = depth[anc[u][0]] + 1;
    for (int i = 1; i < LOG; ++i) anc[u][i] = anc[anc[u][i - 1]][i - 1];
    for (auto &v: adj[u]) {
        if (v == anc[u][0]) continue;
        int id = findEdge(u, v);
        par[v] = id;
        anc[v][0] = u;
        dfs(v);
    }
}

int lca(int u, int v) {
    if (depth[u] < depth[v]) swap(u, v);
    for (int i = LOG - 1; i >= 0; --i) {
        if (depth[anc[u][i]] >= depth[v]) u = anc[u][i];
    }
    if (u == v) return u;
    for (int i = LOG - 1; i >= 0; --i) {
        if (anc[u][i] != anc[v][i]) {
            u = anc[u][i];
            v = anc[v][i];
        }
    }
    return anc[u][0];
}

void dfs2(int u) {
    for (auto &v: adj[u]) {
        if (v == anc[u][0]) continue;
        dfs2(v);
        pref[par[u]] += pref[par[v]];
    }
}

int main() {
    superspeed;
    cin >> numNode;
    for (int i = 1; i < numNode; ++i) {
        int u, v, c1, cfull;
        cin >> u >> v >> c1 >> cfull;
        adj[u].push_back(v);
        adj[v].push_back(u);
        if (u > v) swap(u, v);
        edges[i] = {u, v, c1, cfull};
    }
    sort(edges + 1, edges + numNode);
    dfs(1);
    for (int i = 2; i <= numNode; ++i) {
        int u = i - 1, v = i;
        ++pref[par[u]];
        ++pref[par[v]];
        pref[par[lca(u, v)]] -= 2;
    }
    dfs2(1);
    long long res = 0;
    for (int i = 1; i < numNode; ++i) {
        long long a = 1LL * edges[i].cost1 * pref[i];
        long long b = edges[i].costfull;
        res += min(a, b);
    }
    cout << res << '\n';
    return 0;
}

• Subtask 1: 20 / 20
• Subtask 2: 25 / 25
• Subtask 3: 65 / 65