oj.uz

답안 #369150

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
369150 2021-02-20T14:38:14 Z BartolM 구슬과 끈 (APIO14_beads) C++17
28 / 100
 1000 ms 1024 KB 
#include <bits/stdc++.h>

using namespace std;

#define X first
#define Y second
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <int, pii> pip;
typedef pair <pii, int> ppi;
typedef pair <ll, ll> pll;

const int INF=0x3f3f3f3f;
const ll MAX=(ll)INF*INF;
const int N=1e4+5;

int n;
vector <pii> ls[N];
int dp[N][2];

int rek(int node, int fl, int par) {
    int &ret=dp[node][fl];
    if (ret!=-1) return ret;

    int sum0=0, ed;
    for (pii sus:ls[node]) {
        if (sus.X==par) {
            ed=sus.Y;
            continue;
        }
        sum0+=rek(sus.X, 0, node);
    }
    ret=sum0;
    for (pii sus:ls[node]) {
        if (sus.X==par) continue;
        if (!fl) ret=max(ret, ed+sus.Y+sum0-rek(sus.X, 0, node)+rek(sus.X, 1, node));
    }
    return ret;
}

void load() {
    scanf("%d", &n);
    for (int i=0; i<n-1; ++i) {
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        ls[a].pb(mp(b, c));
        ls[b].pb(mp(a, c));
    }
}

int main() {
    load();
    int sol=0;
    for (int i=1; i<=n; ++i) {
        memset(dp, -1, sizeof dp);
        sol=max(sol, rek(i, 1, 0));
    }
    printf("%d\n", sol);
    return 0;
}

Compilation message

beads.cpp: In function 'void load()':
beads.cpp:44:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   44 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
beads.cpp:47:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   47 |         scanf("%d %d %d", &a, &b, &c);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
beads.cpp: In function 'int rek(int, int, int)':
beads.cpp:38:33: warning: 'ed' may be used uninitialized in this function [-Wmaybe-uninitialized]
   38 |         if (!fl) ret=max(ret, ed+sus.Y+sum0-rek(sus.X, 0, node)+rek(sus.X, 1, node));
      |                                 ^

Subtask #1
13.0 / 13.0

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

Subtask #2
15.0 / 15.0

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

Subtask #3
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 620 KB Output is correct
2 Correct 1 ms 620 KB Output is correct
3 Correct 1 ms 620 KB Output is correct
4 Correct 1 ms 620 KB Output is correct
5 Correct 1 ms 620 KB Output is correct
6 Correct 1 ms 620 KB Output is correct
7 Correct 1 ms 620 KB Output is correct
8 Correct 1 ms 620 KB Output is correct
9 Correct 1 ms 620 KB Output is correct
10 Correct 1 ms 620 KB Output is correct
11 Correct 1 ms 620 KB Output is correct
12 Correct 1 ms 620 KB Output is correct
13 Correct 1 ms 620 KB Output is correct
14 Correct 1 ms 620 KB Output is correct
15 Correct 1 ms 620 KB Output is correct
16 Correct 3 ms 620 KB Output is correct
17 Correct 3 ms 620 KB Output is correct
18 Correct 3 ms 620 KB Output is correct
19 Correct 3 ms 620 KB Output is correct
20 Correct 3 ms 620 KB Output is correct
21 Correct 3 ms 620 KB Output is correct
22 Correct 3 ms 620 KB Output is correct
23 Execution timed out 1094 ms 1024 KB Time limit exceeded
24 Halted 0 ms 0 KB -

Subtask #4
0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 620 KB Output is correct
2 Correct 1 ms 620 KB Output is correct
3 Correct 1 ms 620 KB Output is correct
4 Correct 1 ms 620 KB Output is correct
5 Correct 1 ms 620 KB Output is correct
6 Correct 1 ms 620 KB Output is correct
7 Correct 1 ms 620 KB Output is correct
8 Correct 1 ms 620 KB Output is correct
9 Correct 1 ms 620 KB Output is correct
10 Correct 1 ms 620 KB Output is correct
11 Correct 1 ms 620 KB Output is correct
12 Correct 1 ms 620 KB Output is correct
13 Correct 1 ms 620 KB Output is correct
14 Correct 1 ms 620 KB Output is correct
15 Correct 1 ms 620 KB Output is correct
16 Correct 3 ms 620 KB Output is correct
17 Correct 3 ms 620 KB Output is correct
18 Correct 3 ms 620 KB Output is correct
19 Correct 3 ms 620 KB Output is correct
20 Correct 3 ms 620 KB Output is correct
21 Correct 3 ms 620 KB Output is correct
22 Correct 3 ms 620 KB Output is correct
23 Execution timed out 1094 ms 1024 KB Time limit exceeded
24 Halted 0 ms 0 KB -