답안 #444677

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
444677	2021-07-14T17:59:32 Z	NintsiChkhaidze	Election Campaign (JOI15_election_campaign)	C++14	10 / 100	516 ms	46532 KB

election_campaign

#include <bits/stdc++.h>
#define pb push_back
#define s second
#define f first
#define ll long long
#define pii pair<int,int>
#define left (node<<1),l,((l+r)>>1)
#define right ((node<<1)|1),((l+r)>>1) + 1,r
#define int ll
using namespace std;
const int N = 100005;
int cnt,a[N],d[25][N],dep[N],dp[N],sum[N],in[N];
vector <int> v[N];
set <pii> st;
vector <pair<pii,int> > vec[N];
void dfs(int x,int par){
    dep[x] = dep[par] + 1;
    in[x] = ++cnt;
    d[0][x] = par;
    for (int j = 0; j < v[x].size(); j++){
        int to = v[x][j];
        if (to != par) dfs(to,x);
    }
}
void solve(int x){
    for (int j = 0; j < v[x].size(); j++){
        int to = v[x][j];
        if (to == d[0][x]) continue;
        solve(to);
        sum[x] += dp[to];
    }
    
    dp[x] = sum[x];
    st.clear(); st.insert({N,0});
    for (int j = 0; j < v[x].size(); j++){
        int to = v[x][j];
        if (to == d[0][x]) continue;
        st.insert({in[to],dp[to]});
    }
    
    for (int j = 0; j < vec[x].size(); j++){
        int l = vec[x][j].f.f,r = vec[x][j].f.s;
        int s = vec[x][j].s + sum[x];
        set <pii> :: iterator it; 
        if (l != x){
            s += sum[l];
            it = st.lower_bound({in[l],1e18});
            it--;
            s -= (it->s);
        } 
        
        if (r != x){
            s += sum[r];
            it = st.lower_bound({in[r],1e18});
            it--;
            s -= (it->s);
        } 
        dp[x] = max(dp[x],s);
    }
    //cout<<x<<" ans "<<dp[x]<<endl;
}
int lca(int x,int y){
    if (dep[x] > dep[y]) swap(x,y);
    
    for (int j = 20; j >= 0; j--)
        if (dep[d[j][y]] >= dep[x]) y = d[j][y];
        
    if (x == y) return x;   
    
    for (int j = 20; j >= 0; j--)
        if (d[j][x] != d[j][y]) x = d[j][x],y = d[j][y];
    
    return d[0][x];
}
main (){
    ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);
    int n;
    cin>>n;
    for (int i =1; i <n;i++){
        int a,b;
        cin>>a>>b;
        v[a].pb(b),v[b].pb(a);
    }
    dfs(1,1);
    
    for (int i = 1; i <= 20; i++)
        for (int j = 1; j <= n; j++)
            d[i][j] = d[i - 1][d[i - 1][j]];
    
    int q;
    cin>>q;
    while(q--){
        int x,y,z;
        cin>>x>>y>>z;
        int c = lca(x,y);
        vec[c].pb({{x,y},z});
    }
    
    solve(1);
    cout<<dp[1];
}

Compilation message

election_campaign.cpp: In function 'void dfs(long long int, long long int)':
election_campaign.cpp:20:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |     for (int j = 0; j < v[x].size(); j++){
      |                     ~~^~~~~~~~~~~~~
election_campaign.cpp: In function 'void solve(long long int)':
election_campaign.cpp:26:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |     for (int j = 0; j < v[x].size(); j++){
      |                     ~~^~~~~~~~~~~~~
election_campaign.cpp:35:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |     for (int j = 0; j < v[x].size(); j++){
      |                     ~~^~~~~~~~~~~~~
election_campaign.cpp:41:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<std::pair<long long int, long long int>, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |     for (int j = 0; j < vec[x].size(); j++){
      |                     ~~^~~~~~~~~~~~~~~
election_campaign.cpp: At global scope:
election_campaign.cpp:75:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   75 | main (){
      | ^~~~

Subtask #1
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	5068 KB	Output is correct
2	Correct	3 ms	5152 KB	Output is correct
3	Incorrect	3 ms	5068 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #2
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	5068 KB	Output is correct
2	Correct	3 ms	5068 KB	Output is correct
3	Correct	4 ms	5452 KB	Output is correct
4	Correct	273 ms	46136 KB	Output is correct
5	Correct	214 ms	46348 KB	Output is correct
6	Correct	231 ms	46300 KB	Output is correct
7	Correct	194 ms	46164 KB	Output is correct
8	Correct	210 ms	46228 KB	Output is correct
9	Correct	245 ms	46424 KB	Output is correct
10	Correct	188 ms	46116 KB	Output is correct

Subtask #3
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	5068 KB	Output is correct
2	Correct	3 ms	5068 KB	Output is correct
3	Correct	4 ms	5452 KB	Output is correct
4	Correct	273 ms	46136 KB	Output is correct
5	Correct	214 ms	46348 KB	Output is correct
6	Correct	231 ms	46300 KB	Output is correct
7	Correct	194 ms	46164 KB	Output is correct
8	Correct	210 ms	46228 KB	Output is correct
9	Correct	245 ms	46424 KB	Output is correct
10	Correct	188 ms	46116 KB	Output is correct
11	Correct	16 ms	6696 KB	Output is correct
12	Correct	243 ms	46480 KB	Output is correct
13	Correct	250 ms	46504 KB	Output is correct
14	Correct	234 ms	46488 KB	Output is correct
15	Correct	237 ms	46468 KB	Output is correct
16	Correct	253 ms	46436 KB	Output is correct
17	Correct	202 ms	46464 KB	Output is correct
18	Correct	219 ms	46480 KB	Output is correct
19	Correct	294 ms	46532 KB	Output is correct
20	Correct	211 ms	46496 KB	Output is correct