Submission #223201

#	Time	Username	Problem	Language	Result	Execution time	Memory
223201		dwsc	Putovanje (COCI20_putovanje)	C++14	110 / 110	676 ms	27128 KiB

putovanje

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> ii;
typedef pair<ii,ii> iv;
vector<int> adj[200005];
int heavy[200005],depth[200005],head[200005], p[200005], pos[200005], sz[200005];
int cnt = 0; ///set to 1 if you're using fenwick tree
void dfs(int u){
    sz[u] = 1;
    int maxChild = 0;
    for(int v : adj[u]){
        if(sz[v] == 0){
            depth[v] = depth[u] + 1;
            dfs(v);
            sz[u] += sz[v];
            p[v] = u;
            if(sz[v] > maxChild){
                maxChild = sz[v];
                heavy[u] = v;
            }
        }
    }
}

void decompose(int u, int h){
    head[u] = h;
    pos[u] = cnt;
    cnt++;
    if(heavy[u] != 0) decompose(heavy[u], h);
    for(int v : adj[u]){
        if(sz[v] < sz[u] && v != heavy[u]){
            decompose(v,v);
        }
    }
}
struct node {
    node *l, *r;
    int val, s, m, e, lazyadd;
    node(int _s, int _e): s(_s), e(_e), m((_s+_e)/2), val(0), lazyadd(0), l(NULL), r(NULL) {
        if (s != e) l = new node(s, m), r = new node(m+1, e);
    }
    int value() { //returns the value of the current node after lazy propagating
        if (s == e) return val + lazyadd;
        val += lazyadd;
        l->lazyadd += lazyadd, r->lazyadd += lazyadd;
        lazyadd = 0;
        return val;
    }
    void add(int x, int y, int v) {
        if (x > y) return;
        if (s == x && e == y) lazyadd += v;
        else {
            if (x > m) r->add(x, y, v);
            else if (y <= m) l->add(x, y, v);
            else l->add(x, m, v), r->add(m+1, y, v);
            val = min(l->value(), r->value()); //Change here to max
        }
    }
    int query(int x, int y) {
        value();
        if (s == x && e == y) return value();
        if (x > m) return r->query(x, y);
        if (y <= m) return l->query(x, y);
        return min(l->query(x, m),r->query(m+1, y)); //Change here to max
    }
}*root;
void update(int a,int b){
    //cout << a << " " << b << "\n";
    if(depth[a] > depth[b]) swap(a,b);
    for(;head[a] != head[b];b = p[head[b]]){
        if(depth[head[a]] > depth[head[b]]) swap(a,b);
        root->add(pos[head[b]],pos[b],1);
        ///any update and query affects pos[head[b]] inclusive to pos[b] inclusive
    }
    //cout << a << " " << b << "hi\n";
    //cout << pos[a] << " " << pos[b] << "\n";
    if(depth[a] > depth[b]) swap(a,b);
    root->add(pos[a]+1,pos[b],1);
}
int main(){
    int n;
    cin >> n;
    iv edge[n];
    root = new node(0,n-1);
    for (int i = 0; i < n-1; i++){
        int a,b,x,y;
        cin >> a >> b >> x >> y;
        a--;
        b--;
        edge[i] = iv(ii(a,b),ii(x,y));
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    dfs(0);
    decompose(0,0);
    for (int i = 0; i < n-1; i++) update(i,i+1);
    long long ans = 0;
    for (int i = 0; i < n-1; i++){
        int a = edge[i].first.first,b = edge[i].first.second;
        long long x = edge[i].second.first,y = edge[i].second.second;
        if (depth[a] < depth[b]) swap(a,b);
        int val = root->query(pos[a],pos[a]);
        //cout << a << " " << val << " " << x << " " << y << "\n";
        if (val != 0) ans += min(y,x*val);
    }
    cout << ans;
    ///any update and query affects pos[a]+1 inclusive to pos[b] inclusive
}

Compilation message (stderr)

putovanje.cpp: In constructor 'node::node(int, int)':
putovanje.cpp:38:20: warning: 'node::e' will be initialized after [-Wreorder]
     int val, s, m, e, lazyadd;
                    ^
putovanje.cpp:38:17: warning:   'int node::m' [-Wreorder]
     int val, s, m, e, lazyadd;
                 ^
putovanje.cpp:39:5: warning:   when initialized here [-Wreorder]
     node(int _s, int _e): s(_s), e(_e), m((_s+_e)/2), val(0), lazyadd(0), l(NULL), r(NULL) {
     ^~~~
putovanje.cpp:38:17: warning: 'node::m' will be initialized after [-Wreorder]
     int val, s, m, e, lazyadd;
                 ^
putovanje.cpp:38:9: warning:   'int node::val' [-Wreorder]
     int val, s, m, e, lazyadd;
         ^~~
putovanje.cpp:39:5: warning:   when initialized here [-Wreorder]
     node(int _s, int _e): s(_s), e(_e), m((_s+_e)/2), val(0), lazyadd(0), l(NULL), r(NULL) {
     ^~~~
putovanje.cpp:38:23: warning: 'node::lazyadd' will be initialized after [-Wreorder]
     int val, s, m, e, lazyadd;
                       ^~~~~~~
putovanje.cpp:37:11: warning:   'node* node::l' [-Wreorder]
     node *l, *r;
           ^
putovanje.cpp:39:5: warning:   when initialized here [-Wreorder]
     node(int _s, int _e): s(_s), e(_e), m((_s+_e)/2), val(0), lazyadd(0), l(NULL), r(NULL) {
     ^~~~

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