oj.uz

Submission #702004

# Submission time Handle Problem Language Result Execution time Memory
702004 2023-02-22T13:19:15 Z Do_you_copy Transport (COCI19_transport) C++17
130 / 130
 246 ms 19288 KB 
#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

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.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2952 KB Output is correct
2 Correct 5 ms 3156 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 3284 KB Output is correct
2 Correct 8 ms 3540 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 10172 KB Output is correct
2 Correct 65 ms 9296 KB Output is correct

Subtask #4
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 12724 KB Output is correct
2 Correct 108 ms 14204 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 16504 KB Output is correct
2 Correct 168 ms 19288 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 5832 KB Output is correct
2 Correct 28 ms 5312 KB Output is correct

Subtask #7
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 7884 KB Output is correct
2 Correct 89 ms 7384 KB Output is correct

Subtask #8
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 9448 KB Output is correct
2 Correct 112 ms 9528 KB Output is correct

Subtask #9
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 177 ms 11864 KB Output is correct
2 Correct 183 ms 11728 KB Output is correct

Subtask #10
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 246 ms 14196 KB Output is correct
2 Correct 211 ms 13000 KB Output is correct