oj.uz

Submission #732926

# Submission time Handle Problem Language Result Execution time Memory
732926 2023-04-29T14:50:24 Z onepunchac168 Election Campaign (JOI15_election_campaign) C++14
10 / 100
 189 ms 47308 KB 
// created by Dinh Manh Hung
// onepunchac168
// THPT CHUYEN HA TINH
// HA TINH, VIET NAM

#include <bits/stdc++.h>
using namespace std;

//#pragma GCC optimize("O3,unroll-loops,no-stack-protector")
//#pragma GCC target("sse4,avx2,fma")
#define task ""
#define ldb long double
#define pb push_back
#define fi first
#define se second
#define pc pop_back()
#define all(x) begin(x),end(x)
#define uniquev(v) v.resize(unique(all(v))-v.begin())
#define FOR(i,a,b) for (int i=a;i<=b;i++)
#define cntbit(v) __builtin_popcountll(v)
#define gcd(a,b) __gcd(a,b)
#define lcm(a,b) ((1LL*a*b)/__gcd(a,b))
#define mask(x) (1LL<<(x))
#define readbit(x,i) ((x>>i)&1)
#define ins insert

typedef long long ll;
typedef pair <ll,ll> ii;
typedef pair <ll,ii> iii;
typedef pair <ii,ii> iiii;

ll dx[]= {1,-1,0,0,1,-1,1,-1};
ll dy[]= {0,0,-1,1,1,-1,-1,1};

const ldb PI = acos (-1);
//const ll mod=978846151;
//const ll base=29;
const int maxn=1e6+5;
const int mod=1e9+7;
const char nl = '\n';
inline int ReadInt()
{
    char co;
    for (co = getchar(); co < '0' || co > '9'; co = getchar());
    int xo = co - '0';
    for (co = getchar(); co >= '0' && co <= '9'; co = getchar())
        xo = xo * 10 + co - '0';
    return xo;
}

void WriteInt(int xo)
{
    if (xo > 9)
        WriteInt(xo / 10);
    putchar(xo % 10 + '0');
}
/* END OF TEMPLATE*/

// ================= Solution =================//
const int N=1e5+5;
ll n,m;
vector <ll> vt[N];
vector <iii> tmp[N];
ll parent[N][20];
ll sz[N];
ll dp[N];
ll in[N];
ll out[N];
ll root=0;
ll bit[N];
void update(int u,ll val)
{
    while (u<=n)
    {
        bit[u]+=val;
        u+=u&(-u);
    }
}
ll get(int u)
{
    ll suma=0;
    while (u>0)
    {
        suma+=bit[u];
        u-=u&(-u);
    }
    return suma;
}
void dfsa(int u,int vv)
{
    in[u]=++root;
    for (auto v:vt[u])
    {
        if (v==vv)
        {
            continue;
        }
        parent[v][0]=u;
        for (int i=1;i<=18;i++)
        {
            parent[v][i]=parent[parent[v][i-1]][i-1];
        }
        sz[v]=sz[u]+1;
        dfsa(v,u);
    }
    out[u]=root;
}
ll par[N];
ll findpar(int u)
{
    if (par[u]<0)
    {
        return u;
    }
    return par[u]=findpar(par[u]);
}
void dfs(int u,int vv)
{
    ll sum=0;
    for (auto v:vt[u])
    {
        if (v==vv)
        {
            continue;
        }
        dfs(v,u);
        dp[u]=max(dp[u],dp[v]);
        sum+=dp[v];
    }
    ll gmax=0;
    for (auto v:tmp[u])
    {
        ll ua=v.se.fi;
        ll va=v.se.se;
        ll wa=v.fi;
        ll indexa=get(in[ua])+get(in[va]);
        ll indexb=sum;
        ll a1=findpar(ua);
        ll a2=findpar(va);
        if (a1!=u)
        {
            indexb-=dp[a1];
        }
        if (a2!=u)
        {
            indexb-=dp[a2];
        }
        gmax=max(gmax,indexa+indexb+wa);
    }
    dp[u]=max(dp[u],gmax);
    update(in[u],sum);
    update(in[u]+1,-sum);
    for (auto v:vt[u])
    {
        if (v==vv)
        {
            continue;
        }
        ll aa=findpar(v);
        update(in[v],sum-dp[aa]);
        update(out[v]+1,-sum+dp[aa]);
        par[aa]=u;
    }
}
ll lca(int u,int v)
{
    if (sz[u]>sz[v])
    {
        swap(u,v);
    }
    for (int i=18;i>=0;i--)
    {
        if (sz[v]-mask(i)>=sz[u])
        {
            v=parent[v][i];
        }
    }
    if (u==v){return u;}
    for (int i=18;i>=0;i--)
    {
        if (parent[u][i]!=parent[v][i])
        {
            u=parent[u][i];
            v=parent[v][i];
        }
    }
    if (u!=v)
    {
        u=parent[u][0];
        v=parent[v][0];
    }
    return u;
}
void optmushnpr()
{
    cin>>n;
    for (int i=1;i<=n;i++)
    {
        par[i]=-1;
    }
    for (int i=1;i<n;i++)
    {
        ll u,v;
        cin>>u>>v;
        vt[u].pb(v);
        vt[v].pb(u);
    }
    dfsa(1,-1);
    cin>>m;
    for (int i=1;i<=m;i++)
    {
        ll a,b,c;
        cin>>a>>b>>c;
        ll pp=lca(a,b);
        tmp[pp].pb({c,{a,b}});
    }
    dfs(1,-1);
    cout<<dp[1];
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    if (fopen(task".inp","r")){
    freopen(task".inp","r",stdin);
    freopen(task".out","w",stdout);}
    int t;
    t=1;
    //cin>>t;
    while (t--){optmushnpr();}
}

// goodbye see ya

Compilation message

election_campaign.cpp: In function 'int main()':
election_campaign.cpp:226:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  226 |     freopen(task".inp","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
election_campaign.cpp:227:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  227 |     freopen(task".out","w",stdout);}
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 4 ms 5028 KB Output is correct
4 Incorrect 3 ms 5204 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 5028 KB Output is correct
3 Correct 4 ms 5332 KB Output is correct
4 Correct 152 ms 46996 KB Output is correct
5 Correct 151 ms 46948 KB Output is correct
6 Correct 115 ms 46956 KB Output is correct
7 Correct 150 ms 47040 KB Output is correct
8 Correct 161 ms 46996 KB Output is correct
9 Correct 123 ms 47056 KB Output is correct
10 Correct 149 ms 46936 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 5028 KB Output is correct
3 Correct 4 ms 5332 KB Output is correct
4 Correct 152 ms 46996 KB Output is correct
5 Correct 151 ms 46948 KB Output is correct
6 Correct 115 ms 46956 KB Output is correct
7 Correct 150 ms 47040 KB Output is correct
8 Correct 161 ms 46996 KB Output is correct
9 Correct 123 ms 47056 KB Output is correct
10 Correct 149 ms 46936 KB Output is correct
11 Correct 17 ms 6588 KB Output is correct
12 Correct 144 ms 47272 KB Output is correct
13 Correct 142 ms 47296 KB Output is correct
14 Correct 131 ms 47308 KB Output is correct
15 Correct 149 ms 47268 KB Output is correct
16 Correct 122 ms 47308 KB Output is correct
17 Correct 142 ms 47232 KB Output is correct
18 Correct 189 ms 47204 KB Output is correct
19 Correct 136 ms 47264 KB Output is correct
20 Correct 137 ms 47240 KB Output is correct

Subtask #4
0 / 30.0

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

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 4 ms 5028 KB Output is correct
4 Incorrect 3 ms 5204 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 4 ms 5028 KB Output is correct
4 Incorrect 3 ms 5204 KB Output isn't correct
5 Halted 0 ms 0 KB -