oj.uz

Submission #88877

# Submission time Handle Problem Language Result Execution time Memory
88877 2018-12-09T17:10:01 Z Mercenary Election Campaign (JOI15_election_campaign) C++11
0 / 100
 206 ms 21080 KB 
#include<bits/stdc++.h>

using namespace std;
#define taskname "TEST"
#define pb	push_back
typedef long double ld;
typedef long long ll;
const int maxn = 1e5 + 5;

int n , m;
int dp[maxn] , lost[maxn];
int P[maxn][20] , h[maxn];
int in[maxn] , out[maxn];
int qa[maxn] , qb[maxn] , qc[maxn];
vector<int> adj[maxn] , q[maxn];
void DFS(int u , int par)
{
    static int nTime = 0;
    in[u] = ++nTime;
    for(int c : adj[u])
        if(c != par){
            h[c] = h[u] + 1;
            P[c][0] = u;
            for(int i = 1 ; i < 20 ; ++i)
                P[c][i] = P[P[c][i - 1]][i - 1];
            DFS(c , u);
        }
    out[u] = nTime;
}

int LCA(int u , int v)
{
    if(h[u] < h[v])swap(u ,v);
    for(int i = 0 ; i < 20 ; ++i)
        if(h[u] - (1 << i) >= h[v])u = P[u][i];
    if(u == v)return u;
    for(int i = 19 ; i >= 0 ; --i)
        if(P[u][i] != P[v][i])u = P[u][i] , v = P[v][i];
    return P[u][0];
}

int bit[maxn];

int query(int x)
{
    int res = 0;
    for( ; x > 0 ; x &= x - 1)
        res += bit[x];
    return res;
}

void update(int l , int h , int c)
{
    for( ; l <= n ; l += l & -l)
        bit[l] += c;
    for( ++h ; h <= n ; h += h & -h)
        bit[h] -= c;
}

void DFS1(int u , int par)
{
    int now = 0;
    for(int c : adj[u])
        if(c != par)
        {
            DFS1(c , u);
            now += dp[c];
        }
    dp[u] = now;
    for(int i : q[u]){
        dp[u] = max(dp[u] , now - query(in[qa[i]]) - query(in[qb[i]]) + qc[i]);
    }
    update(in[u],out[u],dp[u]-now);
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	if(fopen(taskname".INP","r"))
        freopen(taskname".INP", "r",stdin) ,
        freopen(taskname".OUT", "w",stdout);
    cin >> n;
    for(int i = 1 ; i < n ; ++i)
    {
        int u , v;cin >> u >> v;
        adj[u].pb(v);adj[v].pb(u);
    }
    DFS(1 , 0);
    cin >> m;
    for(int i = 1 ; i <= m ; ++i)
    {
        cin >> qa[i] >> qb[i] >> qc[i];
        q[LCA(qa[i] , qb[i])].pb(i);
    }
    DFS1(1 , 0);
    cout << dp[1];
}

Compilation message

election_campaign.cpp: In function 'int main()':
election_campaign.cpp:81:44: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         freopen(taskname".INP", "r",stdin) ,
         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~
         freopen(taskname".OUT", "w",stdout);
         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 
election_campaign.cpp:81:44: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 KB Output is correct
2 Correct 6 ms 5240 KB Output is correct
3 Incorrect 6 ms 5296 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

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

Subtask #3
0 / 5.0

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

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 206 ms 21080 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 KB Output is correct
2 Correct 6 ms 5240 KB Output is correct
3 Incorrect 6 ms 5296 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 KB Output is correct
2 Correct 6 ms 5240 KB Output is correct
3 Incorrect 6 ms 5296 KB Output isn't correct
4 Halted 0 ms 0 KB -