Submission #46337

#	Time	Username	Problem	Language	Result	Execution time	Memory
46337		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 > v[N];
vector < long long > w[N];
bool vis[N];
bool used[N][3];
long long state[N][3];
vector < long long > v0,v1,e;
bool used_go[N][2];
long long state_go[N][2];

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

    int i;

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

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

    if(used[pos][cnt]) return state[pos][cnt];

    long long ans=max(recurse(pos+1,cnt)+v0[pos],recurse(pos+1,cnt)+v1[pos]+e[pos]);

    if(cnt>0) ans=max(ans,recurse(pos+1,cnt-1)+v0[pos]+e[pos]);

    used[pos][cnt]=true;
    return state[pos][cnt]=ans;
}

long long go(int node, int f) {
    if(used_go[node][f]) {
        return state_go[node][f];
    }

    used_go[node][f]=true;
    
    if(v[node].empty()) {
        if(f==1) return state_go[node][f]=numeric_limits < int >::min();
        else return state_go[node][f]=0;
    }

    int i;
    vector < long long > tmp0,tmp1;

    for(i=0;i<(int)(v[node].size());i++) {
        tmp0.push_back(go(v[node][i],0));
        tmp1.push_back(go(v[node][i],1));
    }

    v0=tmp0;
    v1=tmp1;
    e=w[node];

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

    if(f==0) {
        return state_go[node][f]=max(recurse(0,0),recurse(0,2));
    }
    else {
        return state_go[node][f]=recurse(0,1);
    }
}

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:88:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
beads.cpp:90: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