oj.uz

답안 #580999

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
580999 2022-06-22T08:03:44 Z 박상훈(#8359) 구슬과 끈 (APIO14_beads) C++17
13 / 100
 1000 ms 1108 KB 
#include <bits/stdc++.h>

typedef long long ll;
using namespace std;
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));
}












/*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;
    sort(C.begin(), C.end(), greater<int>());

    if (C.size()>=1) dp[s][1] += w0 + C[0];
    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);
    }
    dfs(1);
    printf("%d\n", dp[1][0]);
    return 0;
}
*/

Compilation message

beads.cpp: In function 'int main()':
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:49:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   49 |         scanf("%d %d %d", &x, &y, &z);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 161 ms 284 KB Output is correct
3 Correct 275 ms 288 KB Output is correct
4 Correct 268 ms 212 KB Output is correct
5 Correct 181 ms 284 KB Output is correct
6 Correct 204 ms 280 KB Output is correct
7 Correct 208 ms 288 KB Output is correct
8 Correct 258 ms 288 KB Output is correct
9 Correct 251 ms 296 KB Output is correct
10 Correct 348 ms 340 KB Output is correct
11 Correct 275 ms 288 KB Output is correct
12 Correct 254 ms 288 KB Output is correct

Subtask #2
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 161 ms 284 KB Output is correct
3 Correct 275 ms 288 KB Output is correct
4 Correct 268 ms 212 KB Output is correct
5 Correct 181 ms 284 KB Output is correct
6 Correct 204 ms 280 KB Output is correct
7 Correct 208 ms 288 KB Output is correct
8 Correct 258 ms 288 KB Output is correct
9 Correct 251 ms 296 KB Output is correct
10 Correct 348 ms 340 KB Output is correct
11 Correct 275 ms 288 KB Output is correct
12 Correct 254 ms 288 KB Output is correct
13 Execution timed out 1078 ms 1108 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 161 ms 284 KB Output is correct
3 Correct 275 ms 288 KB Output is correct
4 Correct 268 ms 212 KB Output is correct
5 Correct 181 ms 284 KB Output is correct
6 Correct 204 ms 280 KB Output is correct
7 Correct 208 ms 288 KB Output is correct
8 Correct 258 ms 288 KB Output is correct
9 Correct 251 ms 296 KB Output is correct
10 Correct 348 ms 340 KB Output is correct
11 Correct 275 ms 288 KB Output is correct
12 Correct 254 ms 288 KB Output is correct
13 Execution timed out 1078 ms 1108 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #4
0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 161 ms 284 KB Output is correct
3 Correct 275 ms 288 KB Output is correct
4 Correct 268 ms 212 KB Output is correct
5 Correct 181 ms 284 KB Output is correct
6 Correct 204 ms 280 KB Output is correct
7 Correct 208 ms 288 KB Output is correct
8 Correct 258 ms 288 KB Output is correct
9 Correct 251 ms 296 KB Output is correct
10 Correct 348 ms 340 KB Output is correct
11 Correct 275 ms 288 KB Output is correct
12 Correct 254 ms 288 KB Output is correct
13 Execution timed out 1078 ms 1108 KB Time limit exceeded
14 Halted 0 ms 0 KB -