제출 #1107122

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1107122		matu	구슬과 끈 (APIO14_beads)	C++17	13 / 100	1 ms	508 KiB

beads

#include <bits/stdc++.h>
// #include <tr2/dynamic_bitset>
 
using namespace std;
// using namespace tr2;
#pragma GCC optimize("O3,unroll-loops,Ofast")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
const long double eps = 1e-9;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int randgen(int left, int right) {
    return uniform_int_distribution<int>(left, right)(rng);
}
long long randgenll(long long left, long long right) {
    return uniform_int_distribution<long long>(left, right)(rng);
}

typedef long long ll;
typedef long double ld;
const int mod = 1e9 + 7;
struct Mint
{
    int val;
    Mint(int x = 0)
    {
        val = x % mod;
    }
    Mint(long long x)
    {
        val = x % mod;
    }
    Mint operator+(Mint oth)
    {
        return val + oth.val;
    }
    Mint operator*(Mint oth)
    {
        return 1LL * val * oth.val;
    }
    Mint operator-(Mint oth)
    {
        return val - oth.val + mod;
    }
    Mint fp(Mint a, long long n){
        Mint p = 1;
        while(n){
            if(n & 1){
                p = p * a;
            }
            a = a * a;
            n /= 2;
        }
        return p;
    }
    Mint operator/(Mint oth){
        Mint invers = fp(oth, mod - 2);
        return 1LL * val * invers.val;
    }
    friend ostream& operator << (ostream& os, const Mint& lol){
        os << lol.val;
        return os;
    }
};
 
struct AINT{
    vector<pair<ll,Mint>> aint;
    vector<pair<ll,Mint>> lazy;
    pair<ll,Mint> b;
    AINT(int n){
        b = {1e18,Mint(0)};
        aint.assign(n * 4 + 1,make_pair(1e18,Mint(0)));
        lazy.assign(n * 4 + 1, make_pair(1e18, Mint(0)));
    }
    void update(int v, int tl, int tr, int l, int r, pair<ll,Mint> val){
        if(lazy[v].first != 1e18){
            if(aint[v].first == lazy[v].first){
                aint[v].second = aint[v].second + lazy[v].second;
            }else if(aint[v].first > lazy[v].first) aint[v] = lazy[v];
 
            if(tl != tr){
                if(lazy[v * 2].first == lazy[v].first){
                    lazy[v * 2].second = lazy[v *  2].second + lazy[v].second;
                }else if(lazy[v * 2].first > lazy[v].first) lazy[v * 2] = lazy[v];
                
 
                if(lazy[v * 2 + 1].first == lazy[v].first){
                    lazy[v * 2 + 1].second = lazy[v * 2 + 1].second + lazy[v].second;
                }else if(lazy[v * 2 + 1].first > lazy[v].first){
                    lazy[v * 2 + 1] = lazy[v];
                }
            }
            lazy[v] = b;
        }
        if(l <= tl && r >= tr){
            if(aint[v].first == val.first){
                aint[v].second = aint[v].second + val.second;
            }else if(aint[v].first > val.first){
                    aint[v] = val;
            }
 
            if(tl != tr){
                if(lazy[v * 2].first == val.first){
                    lazy[v * 2].second = lazy[v *  2].second + val.second;
                }else if(lazy[v * 2].first > val.first){
                    lazy[v * 2] = val;
                }
                
 
                if(lazy[v * 2 + 1].first == val.first){
                    lazy[v * 2 + 1].second = lazy[v * 2 + 1].second + val.second;
                }else if(lazy[v * 2 + 1].first > val.first){
                    lazy[v * 2 + 1] = val;
                }
            }
            return;
        }
        if(l > tr || r < tl) return;
        int tm = (tl + tr) / 2;
        update(v * 2, tl, tm, l,r , val);
        update(v * 2 + 1, tm + 1, tr, l, r, val);
        
        if(aint[v * 2].first == aint[v * 2 + 1].first){
            aint[v] = aint[v * 2];
            aint[v].second = aint[v].second + aint[v * 2 + 1].second;
        }else{
            if(aint[v * 2].first < aint[v * 2 + 1].first) aint[v] = aint[v * 2];
            else aint[v] = aint[v * 2 + 1];
        }
 
 
    }
    pair<ll,Mint> query(int v, int tl, int tr, int l, int r){
        if(lazy[v].first != 1e18){
            if(aint[v].first == lazy[v].first){
                aint[v].second = aint[v].second + lazy[v].second;
            }else if(aint[v].first > lazy[v].first) aint[v] = lazy[v];
 
            if(tl != tr){
                if(lazy[v * 2].first == lazy[v].first){
                    lazy[v * 2].second = lazy[v *  2].second + lazy[v].second;
                }else if(lazy[v * 2].first > lazy[v].first) lazy[v * 2] = lazy[v];
                
 
                if(lazy[v * 2 + 1].first == lazy[v].first){
                    lazy[v * 2 + 1].second = lazy[v * 2 + 1].second + lazy[v].second;
                }else if(lazy[v * 2 + 1].first > lazy[v].first){
                    lazy[v * 2 + 1] = lazy[v];
                }
            }
            lazy[v] = b;
        }
        if(l <= tl && r >= tr) return aint[v];
        if(l > tr || r < tl) return make_pair(1e18,Mint(0));
        int tm = (tl + tr) / 2;
        pair<ll,Mint> p1 = query(v * 2, tl ,tm, l, r);
        pair<ll,Mint> p2 = query(v * 2 + 1, tm + 1, tr, l,r);
        if(p1.first == p2.first){
            p1.second = p1.second + p2.second;
            return p1;
        }else if(p1.first < p2.first) return p1;
        return p2;
 
        // int tm = (tl + tr) / 2;
        // if(l <= tl && r >= tr) return aint[v];
        // if(l > tr || r < tl) return 0;
        // return max(query(v * 2, tl, tm,l,r), query(v * 2 + 1, tm + 1, tr, l,r));
        
    }
};
struct AIB{
    vector<int> aib;
    AIB(int n){
        aib.assign(n + 1,0);
    
    }
    void update(int pos, int val){
        for(; pos < aib.size(); pos += (pos & -pos)){
            aib[pos] += val;
        }
    }
    int query(int pos){
        int pl = 0;
   
        for(; pos > 0; pos -= (pos & -pos)) pl += aib[pos];
        return pl;
    }
};
 
int red = 0;
int ______________________________________________________________________________________________________________________________________________;

void solve(){
    int n;
    cin >> n;
    vector<vector<pair<int,int>>> liste(n + 1);
    vector<ll> dp1(n + 1), dp2(n + 1);

    for(int i = 1; i < n; i++){
        int u,v,c;
        cin >> u >> v >> c;
        liste[u].push_back({v,c});
        liste[v].push_back({u,c});
    }
    int root = 0;
    function<void(int,int)> dfs = [&](int nod, int p){
        ll sm = 0;
        for(auto i : liste[nod]){
            if(i.first == p) continue;
            dfs(i.first,nod);
            sm += max(dp1[i.first],(ll)dp2[i.first] + i.second);
        }
        if(liste[nod].size() == 1 && nod != root){
            dp2[nod] = -1e18;
        }
        for(auto i : liste[nod]){
            if(i.first == p) continue;
            dp1[nod] += max({dp1[i.first], dp2[i.first] + i.second});
            dp2[nod] = max(dp2[nod], sm - max(dp1[i.first], (ll)dp2[i.first] + i.second) + i.second + dp1[i.first]);
        }
    };
    ll ans = 0;
    vector<int> lol;
    for(int i = 1; i <= n; i++){
        if(liste[i].size() == 1){
            lol.push_back(i);
        }
    }
    random_shuffle(lol.begin(),lol.end());

    for(auto i = 0; i < lol.size() && i * i <= n; i++){
        dp1.assign(n + 1, 0);
        dp2.assign(n + 1, 0);
        root = lol[i];
        dfs(lol[i],lol[i]);
        
        ans = max(ans, dp1[lol[i]]);
    }
    // for(int i = 1; i <= n; i++){
    //     if(liste[i].size() != 1) continue;
        

    //     //cout << dp[i][0] << " ";
    // }
    cout << ans;
}
int32_t main(){
    cin.tie(0)->sync_with_stdio(0);
    int t = 1; 
    if(red) cin >> t;
   
    while(t--){
        solve();
    }
 

}
 
 
/*
 
2 2 2 2 4
1 3 5
 
 
1 30
1 40
120 2 
2 430
100 3 
3 30
100 4 
4 490
100 5 
5 440
40 6 
6 290
50 7 
7 190
290 8 
8 430
50 9 
9 60
190 10 
10 490

10
4 10 2
1 2 21
1 3 13
6 7 1
7 9 5
2 4 3
2 5 8
1 6 55
6 8 34
*/

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

beads.cpp: In member function 'void AIB::update(int, int)':
beads.cpp:176:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  176 |         for(; pos < aib.size(); pos += (pos & -pos)){
      |               ~~~~^~~~~~~~~~~~
beads.cpp: In function 'void solve()':
beads.cpp:229:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  229 |     for(auto i = 0; i < lol.size() && i * i <= n; i++){
      |                     ~~^~~~~~~~~~~~

• Subtask 1: 13 / 13
• Subtask 2: 0 / 15
• Subtask 3: 0 / 29
• Subtask 4: 0 / 43