Submission #1271764

#	Time	Username	Problem	Language	Result	Execution time	Memory
1271764		cbnk32_tuandung	Putovanje (COCI20_putovanje)	C++17	110 / 110	71 ms	24644 KiB

putovanje

/*  _  _   ___   __  ___  ___  _  _  ___  __   ___     _   _  ___   ___  __   _____  _  _  ___       */
/* | || | /_\ \ / / / __|/ _ \| \| |/ __| \ \ / /_\   | | | |/ _ \ / __| \ \ / / _ \| \| |/ __|      */
/* | __ |/ _ \ V /  \__ \ (_) | .` | (_ |  \ V / _ \  | |_| | (_) | (__   \ V / (_) | .` | (_ |      */
/* |_||_/_/_\_\_|___|___/\___/|_|\_|\___|   \_/_/_\_\ _\___/ \___/ \___| _ \_/_\___/|_|\_|\___| ___  */
/* |   \| __| |_   _| || | /_\ \ / / |   \ / _ \_ _| |  \/  | __| \| | || | |  \/  |/ _ \| \| |/ __| */
/* | |) | _|    | | | __ |/ _ \ V /  | |) | (_) | |  | |\/| | _|| .` | __ | | |\/| | (_) | .` | (_ | */
/* |___/|___|   |_| |_||_/_/ \_\_|   |___/ \___/___| |_|  |_|___|_|\_|_||_| |_|  |_|\___/|_|\_|\___| */

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

/*
 
 run
 g++ coci1920_r5_putovanje.cpp -o run.exe && ./run.exe
 g++ coci1920_r5_putovanje.cpp -std=c++1y -o run.exe && ./run.exe
 
 */

#define re exit(0)
#define r0 return 0
#define ll long long
#define ull unsigned long long
#define TASK "."
#define getBit(i, j) (((i) >> (j)) & 1)

typedef vector<int> vi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;

constexpr int MOD = 1000000007;
constexpr int MAX_N = 200000 + 5;
constexpr int LOG = 20;

template<typename T> void minimise(T &abc, T xyz) {
    if (abc > xyz) abc = xyz;
}

template<typename T> void maximise(T &abc, T xyz) {
    if (abc < xyz) abc = xyz;
}

template<typename T> void add(T &abc, T xyz) {
    abc += xyz;
    if (abc >= MOD) abc -= MOD;
    if (abc < 0) abc += MOD;
}

void fileIO() {
    freopen(TASK".INP", "r", stdin);
    freopen(TASK".OUT", "w", stdout);
}

struct Edge {
    int u, v, c1, c2;
} edges[MAX_N];

int N;

vector<pii> adj[MAX_N];

int par[MAX_N][LOG];
int depth[MAX_N];
int tdgc[MAX_N];
int dp[MAX_N];

void initDFS(int u, int p) {
    for (pii v : adj[u]) {
        if (v.first == p) continue;
        depth[v.first] = depth[u] + 1;
        par[v.first][0] = u;
        for (int j = 1; j < LOG; ++j) {
            par[v.first][j] = par[par[v.first][j - 1]][j - 1];
        }
        initDFS(v.first, u);
    }
}

int LCA(int u, int v) {
    if (depth[u] < depth[v]) swap(u, v);
    int d = depth[u] - depth[v];
    for (int j = 0; j < LOG; ++j) {
        if (getBit(d, j)) {
            u = par[u][j];
        }
    }
    if (u == v) return u;
    for (int j = LOG - 1; j >= 0; --j) {
        if (par[u][j] != par[v][j]) {
            u = par[u][j];
            v = par[v][j];
        }
    }
    return par[u][0];
}

void calcDFS(int u, int p, int idx) {
    for (pii v : adj[u]) {
        if (v.first == p) continue;
        calcDFS(v.first, u, v.second);
        tdgc[u] += tdgc[v.first];
    }
    dp[idx] = tdgc[u];
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    // fileIO();
    
    cin >> N;
    for (int i = 1; i < N; ++i) {
        cin >> edges[i].u >> edges[i].v >> edges[i].c1 >> edges[i].c2;
        adj[edges[i].u].push_back({edges[i].v, i});
        adj[edges[i].v].push_back({edges[i].u, i});
    }

    initDFS(1, 0);
    for (int i = 1; i < N; ++i) {
        int tmp = LCA(i, i + 1);
        ++tdgc[i];
        ++tdgc[i + 1];
        tdgc[tmp] -= 2;
    }

    calcDFS(1, 0, 0);
    ll res = 0;
    for (int i = 1; i < N; ++i) {
        res += min(1ll * edges[i].c2, 1ll * edges[i].c1 * dp[i]);
    }

    cout << res;

    cerr << "\nTime elapsed: " << (1.0 * clock() / CLOCKS_PER_SEC) << " s.";
    r0;
}

/*
 Rubi-channnnn~~~
 Haiiii~~~
 Nani ga suki?
 Choco minto... yori mo anata~
 
 Ayumu-channnnn~~~
 Haiiiii~~~
 Nani ga suki?
 Suturuberi fureiba yori mo anata~
 
 Shiki-channnn~~~
 Haiiiii~~~~
 Nani ga suki?
 Kukkie ando krimu yori mo anata~
 
 Minaaaa~~~
 Haiiiiii~~~
 Nani ga suki?
 Mochrion daisuki AI♡SCREAM
*/

Compilation message (stderr)

putovanje.cpp: In function 'void fileIO()':
putovanje.cpp:50:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   50 |     freopen(TASK".INP", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
putovanje.cpp:51:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |     freopen(TASK".OUT", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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