Submission #702004

#	Time	Username	Problem	Language	Result	Execution time	Memory
702004		Do_you_copy	Transport (COCI19_transport)	C++17	130 / 130	246 ms	19288 KiB

Main

#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define faster ios_base::sync_with_stdio(0);
#define int long long
using namespace std;
using ll = long long;
using pii = pair <int, int>;

const int maxN = 1e5 + 1;
int n;
vector <pii> adj[maxN];
int a[maxN];
int sz[maxN];
bool visited[maxN];

void pre_dfs(int u, int p){
    sz[u] = 1;
    for (auto i: adj[u]){
        if (i.fi == p || visited[i.fi]) continue;
        pre_dfs(i.fi, u);
        sz[u] += sz[i.fi];
    }
}

int find_cent(int u, int p, int siz){
    for (auto i: adj[u]){
        if (i.fi == p || visited[i.fi]) continue;
        if (sz[i.fi] > siz / 2) return find_cent(i.fi, u, siz);
    }
    return u;
}

vector <int> s, t;

void dfs(int u, int p, int d, int minn, bool type){
    if (type == 0){
        minn += a[u];
        if (minn >= 0) s.pb(d + a[u]);
    }
    else{
        minn = min(minn, d);
        t.pb(-minn);
    }
    for (auto i: adj[u]){
        if (visited[i.fi] || i.fi == p) continue;
        if (type == 1)
        dfs(i.fi, u, d + a[u] - i.se, minn, type);
        else{
            dfs(i.fi, u, d + a[u] - i.se, min(-i.se, minn - i.se), type);
        }
    }
}

ll ans = 0;
void update(int cent){
    ll res = 0;
    vector <int> S, T;
    for (auto i: adj[cent]){
        s.clear(), t.clear();
        if (visited[i.fi]) continue;
        dfs(i.fi, cent, -i.se, -i.se, 0);
        dfs(i.fi, cent, a[cent] - i.se, 0, 1);
        sort(s.begin(), s.end());
        sort(t.begin(), t.end());
        for (int j: t) T.pb(j);
        for (int j: s){
            res -= upper_bound(t.begin(), t.end(), j) - t.begin();
            S.pb(j);
        }
    }
    S.pb(0);
    T.pb(0);
    sort(S.begin(), S.end());
    sort(T.begin(), T.end());
    for (int j: S){
        res += upper_bound(T.begin(), T.end(), j) - T.begin();
    }
    ans += res;
}

void build_cent(int u){
    pre_dfs(u, u);
    int cent = find_cent(u, u, sz[u]);
    visited[cent] = 1;
    update(cent);
    for (auto i: adj[cent]){
        if (visited[i.fi]) continue;
        build_cent(i.fi);
    }
}

void Init(){
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    for (int i = 1; i < n; ++i){
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].pb({v, w});
        adj[v].pb({u, w});
    }
    build_cent(1);
    cout << ans - n;
}

#define taskname "test"

signed main(){
    faster
    if (fopen(taskname ".inp", "r")){
        freopen(taskname ".inp", "r", stdin);
        freopen(taskname ".out", "w", stdout);
    }
    int tt = 1;
    while (tt--){
        Init();
    }
}

Compilation message (stderr)

transport.cpp: In function 'int main()':
transport.cpp:112:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  112 |         freopen(taskname ".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
transport.cpp:113:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  113 |         freopen(taskname ".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 13 / 13
• Subtask 2: 13 / 13
• Subtask 3: 13 / 13
• Subtask 4: 13 / 13
• Subtask 5: 13 / 13
• Subtask 6: 13 / 13
• Subtask 7: 13 / 13
• Subtask 8: 13 / 13
• Subtask 9: 13 / 13
• Subtask 10: 13 / 13