Submission #1195144

#	Time	Username	Problem	Language	Result	Execution time	Memory
1195144		TgX_2	Sjeckanje (COCI21_sjeckanje)	C++20	0 / 110	2 ms	5184 KiB

Main

/*-----------------------------
        Author : TgX.2
       11Ti - K28 - CHV
-----------------------------*/

#include <bits/stdc++.h>

#define FOR(i, a, b)       for (__typeof(b) i = (a) - ((a) >= (b)) + 1 * ((a) >= (b)); i != (b) - ((a) >= (b)) + 1 * ((a) < (b)); i += 1 - 2 * ((a) >= (b)))
#define FORC(i, a, b, c)   for (__typeof(b) i = (a), _b = (b), _c = (c); i <= _b; i += _c)
#define FORSq(i, a, b)     for (__typeof(b) i = (a), _b = (b); i * i <= _b; ++i)
#define FORSt(i, s)        for (int i = 0, _s = (int)(s.size()); i < _s; ++i)

#define fi                 first
#define se                 second
#define pb                 push_back
#define len(x)             (int)((x).size())
#define all(x)             (x).begin(), (x).end()

#define _                  << " " <<
#define __                 << "\n"
#define ___                << " "

#define file               "temp"
#define ______________TgX______________ main()
#define int                long long
#define intmax             1e9
#define intmin            -1e9
#define llongmax           1e18
#define llongmin          -1e18
#define memo(a, val)       memset((a), (val), sizeof((a)))

using   namespace std;
typedef long long          ll;
typedef unsigned long long ull;
typedef pair<int, int>     pii;
typedef vector<int>        vi;
typedef vector<pii>        vpii;
#define arr(element_type, cnt) array<element_type, (cnt)>

#define db(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); cout << endl; }
void err(istream_iterator<string> it) {}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
    cout << "[ " << *it << " = " << a << " ] ";
    err(++it, args...);
}

template<typename T1, typename T2> ostream& operator << (ostream& out, const pair<T1, T2>& p) {
    return out << "[ " << p.first << " , " << p.second << " ] ";
}

template<class Con, class = decltype(begin(declval<Con>()))>
typename enable_if<!is_same<Con, string>::value, ostream&>::type
operator << (ostream& out, const Con& con) {
    out << "{ ";
    for (auto beg = con.begin(), it = beg; it != con.end(); it++) {
        out << (it == beg ? "" : ", ") << *it;
    }
    return out << " } ";
}

template<typename T1, typename T2> 
bool mini(T1 &a, T2 b)
    {if (a > b) a = b; else return 0; return 1;}

template<typename T1, typename T2> 
bool maxi(T1 &a, T2 b)
    {if (a < b) a = b; else return 0; return 1;}
/*-----------------------------*/

const int maxn = 2e5 + 7;
int n, a[maxn], b[maxn];
vector<array<int, 2>> g[maxn];

struct LCA {
    vector<int> euler, h, d;
    vector<vector<int>> st;
    int timer = 0;

    void dfs(int u, int cnt) {
        d[u] = euler.size();
        euler.push_back(u);
        h[u] = cnt;
        for (auto val : g[u]) {
            if (h[val[0]] == -1) {
                dfs(val[0], cnt + 1);
                euler.push_back(u); 
            }
        }
    }

    #define mmin(x, y) (h[x] < h[y]) ? x : y

    void buildSparseTable() {
        int m = euler.size();
        st.assign(m, vector<int>(20));

        for (int i = 0; i < m; i++) 
            st[i][0] = euler[i];

        for (int j = 1; (1 << j) <= m; j++) 
            for (int i = 0; i + (1 << j) - 1 < m; i++) 
                st[i][j] = mmin(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);

    }

    int query(int l, int r) {
        int j = __lg(r - l + 1);
        return mmin(st[l][j], st[r - (1 << j) + 1][j]);
    }

    int lca(int u, int v) {
        int left = d[u];
        int right = d[v];
        if (left > right) swap(left, right);
        return query(left, right);
    }

    LCA(int n) : h(n + 7, -1), d(n + 7) {
        dfs(1, 0);
        buildSparseTable();
    }
};

int cntt[maxn], cnt[maxn], dp[maxn];

void dfs(int u, int pre, int id) {
    dp[u] = cntt[u];
    for(auto val : g[u]) {
        int v = val[0], idx = val[1];
        if(v == pre) continue;
        dfs(v, u, idx);
        dp[u] += dp[v];
    }
    if (id != -1) cnt[id] = dp[u];
}

void process() {
    cin >> n;
    FOR(i, 1, n - 1) {
        int u, v; cin >> u >> v >> a[i] >> b[i];
        g[u].pb({v, i});
        g[v].pb({u, i});
    }

    LCA lca(n); 
    FOR(i, 2, n) {
        int k = lca.lca(i, i - 1);
        // cout << i _ i - 1 _ k __ ;
        cntt[i]++;
        cntt[i - 1]++;
        cntt[k] -= 2;
    }

    dfs(1, -1, -1);

    // FOR(i, 1, n)
    //     cout << cnt[i] << " ";

    int ans = 0;
    FOR(i, 1, n - 1) {
        ans += min(a[i] * cnt[i], b[i]);
    }

    cout << ans;
}



/*-----------------------------*/
______________TgX______________ {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);  
    if (fopen(file".inp", "r")) {
        freopen(file".inp", "r", stdin);
        freopen(file".out", "w", stdout);
        freopen(file".debug", "w", stderr);
    }
    process();
}


/*==============================+
|INPUT                          |
--------------------------------|

================================+
|OUTPUT                         |
--------------------------------|

===============================*/

Compilation message (stderr)

Main.cpp:24:41: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   24 | #define ______________TgX______________ main()
      |                                         ^~~~
Main.cpp:171:1: note: in expansion of macro '______________TgX______________'
  171 | ______________TgX______________ {
      | ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:175:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  175 |         freopen(file".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:176:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  176 |         freopen(file".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:177:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  177 |         freopen(file".debug", "w", stderr);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 15
• Subtask 2: 0 / 40
• Subtask 3: 0 / 55