oj.uz

Submission #709204

# Submission time Handle Problem Language Result Execution time Memory
709204 2023-03-13T08:12:43 Z Dan4Life Election Campaign (JOI15_election_campaign) C++17
10 / 100
 1000 ms 13208 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2676 KB Output is correct
4 Correct 12 ms 2760 KB Output is correct
5 Correct 427 ms 8328 KB Output is correct
6 Correct 84 ms 9164 KB Output is correct
7 Correct 382 ms 11884 KB Output is correct
8 Correct 428 ms 8048 KB Output is correct
9 Correct 878 ms 13208 KB Output is correct
10 Correct 334 ms 8144 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Incorrect 2 ms 2644 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Incorrect 2 ms 2644 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1047 ms 9696 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2676 KB Output is correct
4 Correct 12 ms 2760 KB Output is correct
5 Correct 427 ms 8328 KB Output is correct
6 Correct 84 ms 9164 KB Output is correct
7 Correct 382 ms 11884 KB Output is correct
8 Correct 428 ms 8048 KB Output is correct
9 Correct 878 ms 13208 KB Output is correct
10 Correct 334 ms 8144 KB Output is correct
11 Execution timed out 1068 ms 2772 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #6
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2676 KB Output is correct
4 Correct 12 ms 2760 KB Output is correct
5 Correct 427 ms 8328 KB Output is correct
6 Correct 84 ms 9164 KB Output is correct
7 Correct 382 ms 11884 KB Output is correct
8 Correct 428 ms 8048 KB Output is correct
9 Correct 878 ms 13208 KB Output is correct
10 Correct 334 ms 8144 KB Output is correct
11 Correct 2 ms 2644 KB Output is correct
12 Incorrect 2 ms 2644 KB Output isn't correct
13 Halted 0 ms 0 KB -