Submission #1106045

#	Time	Username	Problem	Language	Result	Execution time	Memory
1106045		modwwe	Election Campaign (JOI15_election_campaign)	C++17	100 / 100	157 ms	41668 KiB

election_campaign

#pragma GCC optimize("Ofast,unroll-loops")
//#pragma GCC optimize("conserve-stack")
#include<bits/stdc++.h>
#define int long long
#define ll long long
#define down cout<<'\n';
#define debug cout<<" cucuucucuuu",down
#define NHP     ios_base::sync_with_stdio(0);cout.tie(0);cin.tie(0);
#define modwwe  int t;cin>>t; while(t--)
#define bit(i,j) (i>>j&1)
#define sobit(a) __builtin_popcountll(a)
#define task "test"
#define fin(x) freopen(x".inp","r",stdin)
#define fou(x) freopen(x".ans","w",stdout)
#define pb push_back
#define mask(i) (1<<i)
#define checktime   cerr << (double)clock() / CLOCKS_PER_SEC * 1000  << " ms";
using namespace std;
#define getchar_unlocked getchar

inline int scan()
{
    char c = getchar_unlocked();
    int x = 0;
    while (c < '0' || c > '9')
    {
        c = getchar_unlocked();
    }
    while (c >= '0' && c <= '9')
    {
        x = (x << 1) + (x << 3) + c - '0';
        c = getchar_unlocked();
    }
    return x;
};
void phongbeo();
const int inf = 1e18;
const int mod2 = 1e9+7;
const int  mod1 = 998244353;
const int base=67;
int add(int x,int y)
{
    if(x+y>=mod2) x-=mod2;
    if(x+y<0) x+=mod2;
    return x+y;
}
struct icd
{
    long double a;
    int b;
};
struct ib
{
    int a;
    int b;
};
struct ic
{
    int a, b, c, d;
};
struct ie
{
    int a, b, c, d, e;

};

int  n, m, s1, s2, s4, s3, sf, k, s5, s6, mx, s7, s8, s9, mx2, res, dem2 = 0, dem = 0, s33, dem3, dem4, mid, l2, r2, center;
int  i, s10, s12,k1,k2,k3,s11,limit,w,l,r,last,root,cost;
int kk,invf;
int el = 19;

main()
{
    if(fopen(task".inp","r"))
    {
        fin(task);
        //fou(task);
    }
    NHP
    /// cin>>s1;
    // modwwe
    phongbeo(),down
    // checktime
}
int dp[100001];
int st[17][100001];
int in[100001];
int ou[100001];
vector<int>v[100001];
vector<ic> v2[100001];
struct fen_wick
{
    int bit[100001];
    void upd(int x,int y,int z)
    {
        y++;
        for(x; x<=n; x+=x&-x)
            bit[x]+=z;
        for(y; y<=n; y+=y&-y)
            bit[y]-=z;
    }
    int get(int x)
    {
        int s=0;
        for(x; x; x-=x&-x)
            s+=bit[x];
        return s;
    }
} fen;
bool check(int x,int y)
{
    if(in[x]<=in[y]&&ou[x]>=in[y]) return 0;
    else return 1;
}
int lca(int x,int y)
{
    if(!check(x,y)) return x;
    for(int j=16; j>=0; --j)
        if(check(st[j][x],y))
            x=st[j][x];
    return st[0][x];
}
void dfs(int x,int y)
{
    st[0][x]=y;
    in[x]=++dem;
    for(auto f:v[x])
        if(f!=y)
            dfs(f,x);
    ou[x]=dem;
}
void dfs2(int x,int y)
{
    for(auto f:v[x])
        if(f!=y)
            dfs2(f,x),
                 dp[x]+=dp[f],
                        fen.upd(in[f],ou[f],-dp[f]);
    /// if choose con cua f thi -dpf :D
    s5=0;
    for(auto f:v2[x])
        s2=fen.get(in[f.a])+fen.get(in[f.b])+f.c,
        s5=max(s5,s2);
    /// choose f.a and f.b +?cost
    fen.upd(in[x],in[x],dp[x]);
    dp[x]+=s5;
    for(auto f:v[x])
        if(f!=y)
        {
            fen.upd(in[x]+1,ou[x],dp[f]);
            ///+x-x=0
            /*
            fen.upd(in[f],ou[f],dp[f]);
            fen.upd(in[f],ou[f],-dp[f]);
            */
        }
}
void phongbeo()
{
    cin>>n;
    for(int i=2; i<=n; i++)
    {
        cin>>l>>r;
        v[l].pb(r);
        v[r].pb(l);
    }
    dfs(1,0);
    ou[0]=dem;
    for(int i=1; i<17; i++)
        for(int j=1; j<=n; j++)
            st[i][j]=st[i-1][st[i-1][j]];
    cin>>m;
    for(int i=1; i<=m; i++)
    {
        cin>>l>>r>>s2;
        v2[lca(l,r)].pb({l,r,s2});
    }
    dfs2(1,0);
    cout<<dp[1];
}

Compilation message (stderr)

election_campaign.cpp:72:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   72 | main()
      | ^~~~
election_campaign.cpp: In member function 'void fen_wick::upd(long long int, long long int, long long int)':
election_campaign.cpp:97:13: warning: statement has no effect [-Wunused-value]
   97 |         for(x; x<=n; x+=x&-x)
      |             ^
election_campaign.cpp:99:13: warning: statement has no effect [-Wunused-value]
   99 |         for(y; y<=n; y+=y&-y)
      |             ^
election_campaign.cpp: In member function 'long long int fen_wick::get(long long int)':
election_campaign.cpp:105:13: warning: statement has no effect [-Wunused-value]
  105 |         for(x; x; x-=x&-x)
      |             ^
election_campaign.cpp: In function 'int main()':
election_campaign.cpp:13:23: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 | #define fin(x) freopen(x".inp","r",stdin)
      |                ~~~~~~~^~~~~~~~~~~~~~~~~~~
election_campaign.cpp:76:9: note: in expansion of macro 'fin'
   76 |         fin(task);
      |         ^~~

• Subtask 1: 10 / 10
• Subtask 2: 5 / 5
• Subtask 3: 5 / 5
• Subtask 4: 30 / 30
• Subtask 5: 10 / 10
• Subtask 6: 40 / 40