Submission #46183

#	Time	Username	Problem	Language	Result	Execution time	Memory
46183		Extazy	Beads and wires (APIO14_beads)	C++17	0 / 100	15 ms	14464 KiB

beads

#include <bits/stdc++.h>
#define endl '\n'

using namespace std;

const int N = 200007;

int n;
vector < pair < int, int > > g[N];
vector < int > children[N],weights[N];
bool vis[N];
int dp[N][2];
bool used[N][2][2];
long long state[N][2][2];
vector < int > v0,v1,e;

void dfs(int node) {
    vis[node]=true;

    for(int i=0;i<(int)(g[node].size());i++) if(!vis[g[node][i].first]) {
        children[node].push_back(g[node][i].first);
        weights[node].push_back(g[node][i].second);
        dfs(g[node][i].first);
    }
}

long long recurse(int pos, int parity, int need) {
    if(pos==(int)(e.size())) {
        if(need==0 && parity==0) return 0;
        return numeric_limits < int >::min();
    }

    if(used[pos][parity][need]) return state[pos][parity][need];

    long long ans=numeric_limits < int >::min();
    
    //Take it with zero
    ans=max(ans,recurse(pos+1,parity,need)+v0[pos]+e[pos]);

    //Take it with one
    ans=max(ans,recurse(pos+1,parity^1,need)+v1[pos]+e[pos]);

    ans=max(ans,recurse(pos+1,parity,need)+v1[pos]+e[pos]);

    //Take it with zero but add the edge
    if(need) ans=max(ans,recurse(pos+1,parity,0)+v0[pos]+e[pos]);

    used[pos][parity][need]=true;
    return state[pos][parity][need]=ans;
}

long long go(int node, int f) {
    if(children[node].empty()) {
        if(f==1) return numeric_limits < int >::min();
        else return 0;
    }

    v0.clear();
    v1.clear();
    e=weights[node];

    for(int i=0;i<(int)(children[node].size());i++) {
        v0.push_back(go(children[node][i],0));
        v1.push_back(go(children[node][i],1));
    }

    for(int i=0;i<(int)(children[node].size());i++) {
        used[i][0][0]=used[i][0][1]=used[i][1][0]=used[i][1][1]=false;
    }

    return recurse(0,0,f);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int i,x,y,z;

    scanf("%d", &n);
    for(i=1;i<n;i++) {
        scanf("%d %d %d", &x, &y, &z);
        g[x].push_back(make_pair(y,z));
        g[y].push_back(make_pair(x,z));
    }

    dfs(1);

    printf("%lld\n", go(1,0));

    return 0;
}

Compilation message (stderr)

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

• Subtask 1: 0 / 13
• Subtask 2: 0 / 15
• Subtask 3: 0 / 29
• Subtask 4: 0 / 43