oj.uz

Submission #581009

# Submission time Handle Problem Language Result Execution time Memory
581009 2022-06-22T08:15:46 Z 박상훈(#8359) Beads and wires (APIO14_beads) C++17
28 / 100
 1000 ms 5204 KB 
#include <bits/stdc++.h>

typedef long long ll;
using namespace std;
vector<pair<int, int>> adj[200200];
int dp[200200][2];

void dfs(int s, int pa = -1, int w0 = 0){
    vector<int> C;
    for (auto &[v, w]:adj[s]) if (v!=pa){
        dfs(v, s, w);
        C.push_back(dp[v][0] + w - dp[v][1]);
        dp[s][0] += dp[v][1];
        dp[s][1] += dp[v][1];
    }
    if (C.empty()) return;
    int tmp = *max_element(C.begin(), C.end());

    if (C.size()>=1) dp[s][1] += w0 + tmp;
    //if (C.size()>=2) dp[s][0] = max(dp[s][0], dp[s][0] + C[0] + C[1]);
    dp[s][1] = max(dp[s][0], dp[s][1]);

    //printf("%d: %d %d\n", s, dp[s][0], dp[s][1]);
}

int main(){
    int n;
    scanf("%d", &n);
    for (int i=0;i<n-1;i++){
        int x, y, z;
        scanf("%d %d %d", &x, &y, &z);
        adj[x].emplace_back(y, z);
        adj[y].emplace_back(x, z);
    }
    int ans = 0;
    for (int i=1;i<=n;i++){
        dfs(i);
        ans = max(ans, dp[i][0]);
        for (int i=1;i<=n;i++) dp[i][0] = dp[i][1] = 0;
    }
    printf("%d\n", ans);
    return 0;
}

/*
struct Edge{
    int s, w;
    Edge(){}
    Edge(int _s, int _w): s(_s), w(_w) {}
};
int n;

void _remove(vector<vector<Edge>> &adj, int x, int y){
    for (auto iter = adj[x].begin();iter!=adj[x].end();iter++) if (iter->s==y) {adj[x].erase(iter); break;}
    for (auto iter = adj[y].begin();iter!=adj[y].end();iter++) if (iter->s==x) {adj[y].erase(iter); break;}
}

int bct(vector<vector<Edge>> adj){
    bool flag = 0;
    for (int i=1;i<=n;i++) if (!adj[i].empty()) flag = 1;
    if (!flag) return 0;
    int ret = 0;

    for (int i=1;i<=n;i++){
        if (adj[i].size()==1){
            vector<vector<Edge>> nxt = adj;
            _remove(nxt, i, adj[i][0].s);
            ret = max(ret, bct(nxt));
        }
        else if (adj[i].size()==2 && adj[i][0].w > 0 && adj[i][1].w > 0){
            vector<vector<Edge>> nxt = adj;
            int tmp = adj[i][0].w + adj[i][1].w;
            _remove(nxt, i, adj[i][0].s);
            _remove(nxt, i, adj[i][1].s);
            nxt[adj[i][0].s].emplace_back(adj[i][1].s, -1);
            nxt[adj[i][1].s].emplace_back(adj[i][0].s, -1);

            ret = max(ret, bct(nxt) + tmp);
        }
    }
    return ret;
}

int main(){
    scanf("%d", &n);

    vector<vector<Edge>> adj(n+1, vector<Edge>());
    for (int i=0;i<n-1;i++){
        int x, y, z;
        scanf("%d %d %d", &x, &y, &z);
        adj[x].emplace_back(y, z);
        adj[y].emplace_back(x, z);
    }
    printf("%d\n", bct(adj));
}




*/

Compilation message

beads.cpp: In function 'int main()':
beads.cpp:28:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
beads.cpp:31:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 |         scanf("%d %d %d", &x, &y, &z);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 4 ms 4948 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 2 ms 4948 KB Output is correct
7 Correct 3 ms 4948 KB Output is correct
8 Correct 2 ms 4948 KB Output is correct
9 Correct 3 ms 4948 KB Output is correct
10 Correct 3 ms 4948 KB Output is correct
11 Correct 3 ms 4948 KB Output is correct
12 Correct 4 ms 4988 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 4 ms 4948 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 2 ms 4948 KB Output is correct
7 Correct 3 ms 4948 KB Output is correct
8 Correct 2 ms 4948 KB Output is correct
9 Correct 3 ms 4948 KB Output is correct
10 Correct 3 ms 4948 KB Output is correct
11 Correct 3 ms 4948 KB Output is correct
12 Correct 4 ms 4988 KB Output is correct
13 Correct 5 ms 4948 KB Output is correct
14 Correct 4 ms 4948 KB Output is correct
15 Correct 3 ms 4948 KB Output is correct
16 Correct 5 ms 4988 KB Output is correct
17 Correct 5 ms 4948 KB Output is correct
18 Correct 5 ms 5008 KB Output is correct
19 Correct 4 ms 4948 KB Output is correct
20 Correct 3 ms 4948 KB Output is correct
21 Correct 4 ms 5008 KB Output is correct
22 Correct 4 ms 4924 KB Output is correct

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 4 ms 4948 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 2 ms 4948 KB Output is correct
7 Correct 3 ms 4948 KB Output is correct
8 Correct 2 ms 4948 KB Output is correct
9 Correct 3 ms 4948 KB Output is correct
10 Correct 3 ms 4948 KB Output is correct
11 Correct 3 ms 4948 KB Output is correct
12 Correct 4 ms 4988 KB Output is correct
13 Correct 5 ms 4948 KB Output is correct
14 Correct 4 ms 4948 KB Output is correct
15 Correct 3 ms 4948 KB Output is correct
16 Correct 5 ms 4988 KB Output is correct
17 Correct 5 ms 4948 KB Output is correct
18 Correct 5 ms 5008 KB Output is correct
19 Correct 4 ms 4948 KB Output is correct
20 Correct 3 ms 4948 KB Output is correct
21 Correct 4 ms 5008 KB Output is correct
22 Correct 4 ms 4924 KB Output is correct
23 Execution timed out 1082 ms 5204 KB Time limit exceeded
24 Halted 0 ms 0 KB -

Subtask #4
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 4 ms 4948 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 2 ms 4948 KB Output is correct
7 Correct 3 ms 4948 KB Output is correct
8 Correct 2 ms 4948 KB Output is correct
9 Correct 3 ms 4948 KB Output is correct
10 Correct 3 ms 4948 KB Output is correct
11 Correct 3 ms 4948 KB Output is correct
12 Correct 4 ms 4988 KB Output is correct
13 Correct 5 ms 4948 KB Output is correct
14 Correct 4 ms 4948 KB Output is correct
15 Correct 3 ms 4948 KB Output is correct
16 Correct 5 ms 4988 KB Output is correct
17 Correct 5 ms 4948 KB Output is correct
18 Correct 5 ms 5008 KB Output is correct
19 Correct 4 ms 4948 KB Output is correct
20 Correct 3 ms 4948 KB Output is correct
21 Correct 4 ms 5008 KB Output is correct
22 Correct 4 ms 4924 KB Output is correct
23 Execution timed out 1082 ms 5204 KB Time limit exceeded
24 Halted 0 ms 0 KB -