제출 #88877

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
88877		Mercenary	Election Campaign (JOI15_election_campaign)	C++11	0 / 100	206 ms	21080 KiB

election_campaign

#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];
}

컴파일 시 표준 에러 (stderr) 메시지

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
• Subtask 2: 0 / 5
• Subtask 3: 0 / 5
• Subtask 4: 0 / 30
• Subtask 5: 0 / 10
• Subtask 6: 0 / 40