oj.uz

답안 #563475

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
563475 2022-05-17T10:03:29 Z piOOE 구슬과 끈 (APIO14_beads) C++17
28 / 100
 1000 ms 5716 KB 
//#define _GLIBCXX_DEBUG

//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#include <bits/stdc++.h>

using namespace std;

//#include <ext/pb_ds/assoc_container.hpp>
//
//using namespace __gnu_pbds;
//
//template<typename T>
//using ordered_set = tree<T, null_type, less < T>, rb_tree_tag, tree_order_statistics_node_update>;

//template<typename T>
//using normal_queue = priority_queue<T, vector<T>, greater<>>;

mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

#define trace(x) cout << #x << ": " << (x) << endl;
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define uniq(x) x.resize(unique(all(x)) - begin(x))
#define sz(s) ((int) size(s))
#define pii pair<int, int>
#define mp(x, y) make_pair(x, y)
#define int128 __int128
#define pb push_back
#define popb pop_back
#define eb emplace_back
#define fi first
#define se second
#define itn int

typedef long long ll;
typedef pair<ll, ll> pll;
typedef long double ld;
typedef double db;
typedef unsigned int uint;


template<typename T>
bool ckmn(T &x, T y) {
    if (x > y) {
        x = y;
        return true;
    }
    return false;
}

template<typename T>
bool ckmx(T &x, T y) {
    if (x < y) {
        x = y;
        return true;
    }
    return false;
}

int bit(int x, int b) {
    return (x >> b) & 1;
}

int rand(int l, int r) { return (int) ((ll) rnd() % (r - l + 1)) + l; }


const ll infL = 3e18;
const int infI = 1000000000 + 7;
const int infM = 0x3f3f3f3f; //a little bigger than 1e9
const ll infML = 0x3f3f3f3f3f3f3f3fLL; //4.5e18
const int N = 200002;
const int mod = 998244353;
const ld eps = 1e-9;

vector<pair<int, int>> g[N];

ll dp[2][N];

int p[N], wp[N];

void precalc(int v, int par) {
    p[v] = par;
    for (auto [to, w]: g[v]) {
        if (to != par) {
            wp[to] = w;
            precalc(to, v);
        }
    }
}

void dfs(int v) {
    dp[0][v] = dp[1][v] = 0;
    ll nw = -infL;
    for (auto [to, w]: g[v]) {
        if (to != p[v]) {
            dfs(to);
            ll val = max(dp[1][to], dp[0][to]);
            dp[0][v] += val;
            ckmx(nw, dp[0][to] + w - val);
        }
    }
    if (p[v] != -1)
        ckmx(dp[1][v], dp[0][v] + nw + wp[v]);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    for (int i = 1; i < n; ++i) {
        int a, b, w;
        cin >> a >> b >> w;
        --a, --b;
        g[a].emplace_back(b, w);
        g[b].emplace_back(a, w);
    }
    ll ans = -infL;
    for (int i = 0; i < n; ++i) {
        if (g[i].size() == 1) {
            precalc(i, -1);
            dfs(i);
            ckmx(ans, max(dp[1][i], dp[0][i]));
        }
    }
    cout << ans;
    return 0;
}

Subtask #1
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 5028 KB Output is correct
3 Correct 3 ms 5024 KB Output is correct
4 Correct 3 ms 5028 KB Output is correct
5 Correct 3 ms 5028 KB Output is correct
6 Correct 3 ms 5024 KB Output is correct
7 Correct 3 ms 4948 KB Output is correct
8 Correct 3 ms 4948 KB Output is correct
9 Correct 3 ms 5032 KB Output is correct
10 Correct 3 ms 5024 KB Output is correct
11 Correct 4 ms 5028 KB Output is correct
12 Correct 3 ms 4948 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 5028 KB Output is correct
3 Correct 3 ms 5024 KB Output is correct
4 Correct 3 ms 5028 KB Output is correct
5 Correct 3 ms 5028 KB Output is correct
6 Correct 3 ms 5024 KB Output is correct
7 Correct 3 ms 4948 KB Output is correct
8 Correct 3 ms 4948 KB Output is correct
9 Correct 3 ms 5032 KB Output is correct
10 Correct 3 ms 5024 KB Output is correct
11 Correct 4 ms 5028 KB Output is correct
12 Correct 3 ms 4948 KB Output is correct
13 Correct 3 ms 4948 KB Output is correct
14 Correct 4 ms 5024 KB Output is correct
15 Correct 3 ms 4948 KB Output is correct
16 Correct 4 ms 4948 KB Output is correct
17 Correct 3 ms 4948 KB Output is correct
18 Correct 4 ms 4948 KB Output is correct
19 Correct 5 ms 4948 KB Output is correct
20 Correct 5 ms 4948 KB Output is correct
21 Correct 4 ms 4948 KB Output is correct
22 Correct 3 ms 5028 KB Output is correct

Subtask #3
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 5028 KB Output is correct
3 Correct 3 ms 5024 KB Output is correct
4 Correct 3 ms 5028 KB Output is correct
5 Correct 3 ms 5028 KB Output is correct
6 Correct 3 ms 5024 KB Output is correct
7 Correct 3 ms 4948 KB Output is correct
8 Correct 3 ms 4948 KB Output is correct
9 Correct 3 ms 5032 KB Output is correct
10 Correct 3 ms 5024 KB Output is correct
11 Correct 4 ms 5028 KB Output is correct
12 Correct 3 ms 4948 KB Output is correct
13 Correct 3 ms 4948 KB Output is correct
14 Correct 4 ms 5024 KB Output is correct
15 Correct 3 ms 4948 KB Output is correct
16 Correct 4 ms 4948 KB Output is correct
17 Correct 3 ms 4948 KB Output is correct
18 Correct 4 ms 4948 KB Output is correct
19 Correct 5 ms 4948 KB Output is correct
20 Correct 5 ms 4948 KB Output is correct
21 Correct 4 ms 4948 KB Output is correct
22 Correct 3 ms 5028 KB Output is correct
23 Correct 648 ms 5404 KB Output is correct
24 Correct 655 ms 5396 KB Output is correct
25 Correct 634 ms 5404 KB Output is correct
26 Execution timed out 1092 ms 5716 KB Time limit exceeded
27 Halted 0 ms 0 KB -

Subtask #4
0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 5028 KB Output is correct
3 Correct 3 ms 5024 KB Output is correct
4 Correct 3 ms 5028 KB Output is correct
5 Correct 3 ms 5028 KB Output is correct
6 Correct 3 ms 5024 KB Output is correct
7 Correct 3 ms 4948 KB Output is correct
8 Correct 3 ms 4948 KB Output is correct
9 Correct 3 ms 5032 KB Output is correct
10 Correct 3 ms 5024 KB Output is correct
11 Correct 4 ms 5028 KB Output is correct
12 Correct 3 ms 4948 KB Output is correct
13 Correct 3 ms 4948 KB Output is correct
14 Correct 4 ms 5024 KB Output is correct
15 Correct 3 ms 4948 KB Output is correct
16 Correct 4 ms 4948 KB Output is correct
17 Correct 3 ms 4948 KB Output is correct
18 Correct 4 ms 4948 KB Output is correct
19 Correct 5 ms 4948 KB Output is correct
20 Correct 5 ms 4948 KB Output is correct
21 Correct 4 ms 4948 KB Output is correct
22 Correct 3 ms 5028 KB Output is correct
23 Correct 648 ms 5404 KB Output is correct
24 Correct 655 ms 5396 KB Output is correct
25 Correct 634 ms 5404 KB Output is correct
26 Execution timed out 1092 ms 5716 KB Time limit exceeded
27 Halted 0 ms 0 KB -