Submission #709204

#	Time	Username	Problem	Language	Result	Execution time	Memory
709204		Dan4Life	Election Campaign (JOI15_election_campaign)	C++17	10 / 100	1068 ms	13208 KiB

election_campaign

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define int long long
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) a.begin(),a.end()
const int mxN = (int)1e5+10;
const int LINF = (int)1e18;
int n, m, x, y;
vector<int> adj[mxN];
int a[mxN], b[mxN], c[mxN], node[mxN];
bool bad[20][20];

bool dfs(int s, int t, int v, int p){
    if(s==t) return true;
    for(auto u : adj[s]){
        if(u==p) continue;
        if(dfs(u,t,v,s)){ node[u]+=v; return 1; }
    }
    return 0;
}

void add(int s, int t, int v){
    // this can be done in O(logN) or O(1) with sparse tables...
    node[s]+=v; dfs(s,t,v,-1);
}

int32_t main()
{
    ios_base::sync_with_stdio(false); cin.tie(0);
    cin >> n; int ans = 0;
    for(int i = 1; i < n; i++){
        int x, y; cin >> x >> y;
        adj[x].pb(y), adj[y].pb(x);
    }
    cin >> m;
    for(int i = 0; i < m; i++) cin >> a[i] >> b[i] >> c[i];
    for(int i = 0; i < m; i++){
        for(int j = i+1; j < m; j++){
            add(a[i],b[i],1),  add(a[j],b[j],1);
            bad[i][j]=bad[j][i]=(*max_element(node+1,node+n+1)>=2);
            add(a[i],b[i],-1),  add(a[j],b[j],-1);
        }
    }
    for(int mask = 1; mask < (1<<m); mask++){
        vector<int> v; v.clear(); bool ok = 0;
        for(int i = 0; i < m; i++) if((mask>>i)&1) v.pb(i);
        for(int i = 0; i < sz(v); i++)
            for(int j = i+1; j < sz(v); j++)
                ok|=bad[v[i]][v[j]];
        if(ok) continue; int sum = 0;
        for(auto u : v) sum+=c[u];
        ans = max(ans, sum);
    }
    cout << ans;
}

• Subtask 1: 10 / 10
• Subtask 2: 0 / 5
• Subtask 3: 0 / 5
• Subtask 4: 0 / 30
• Subtask 5: 0 / 10
• Subtask 6: 0 / 40