oj.uz

답안 #747892

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
747892 2023-05-25T06:34:42 Z FulopMate Janjetina (COCI21_janjetina) C++17
15 / 110
 1500 ms 5716 KB 
#include <bits/stdc++.h>

// #define MULTI_TEST_CASE
// #define TEST_TEXT

using namespace std;

#define ll long long
#define MAX(a, b) (a) = max((a), (b))
#define MIN(a, b) (a) = min((a), (b))
#define all(a) (a).begin(), (a).end()
#define sortedpair(a, b) {min((a), (b)), max((a), (b))}

const ll MOD = 1e9+7;

struct edge {
    int to, w;
};

int n, k;
vector<vector<edge>> v;
ll ans = 0;
vector<bool> voltcentroid;
vector<int> siz;
const int st_size = 262144;
vector<ll> st_ut, st_ut_max;

void add(vector<ll> &st, int d, int ind = 1, int l = 0, int r = st_size-1){
    if(l == r){
        st[ind]++;
        return;
    }
    int mid = (l+r)/2;
    if(d <= mid) add(st, d, ind*2, l, mid);
    else add(st, d, ind*2+1, mid+1, r);
    st[ind] = st[ind*2] + st[ind*2+1];
}

ll query(vector<ll> &st, int ql, int qr, int ind = 1, int l = 0, int r = st_size-1){
    if(qr < ql)return 0;
    if(r < ql || l > qr)return 0;
    if(ql <= l && r <= qr) return st[ind];
    int mid = (l+r)/2;
    return query(st, ql, qr, ind*2, l, mid) + query(st, ql, qr, ind*2+1, mid+1, r);
}

int c_szamoz(int x, int p = -1){
    if(voltcentroid[x])return 0;
    int cur = 1;
    for(edge&i : v[x]){
        if(i.to == p)continue;
        cur += c_szamoz(i.to, x);
    }
    return siz[x] = cur;
}

int c_keres(int x, int meret, int p = -1){
    for(edge&i : v[x]){
        if(i.to == p)continue;
        if(!voltcentroid[i.to]){
            if(siz[i.to] > meret/2){
                return c_keres(i.to, meret, x);
            }
        }
    }
    return x;
}

// void c_szamol(int x, int mx_w, int d, int p = -1){
//     ans += query(st_ut, 0, mx_w-d-k);
//     ans += query(st_ut_max, d+k, 2001);
//     for(edge&i : v[x]){
//         if(i.to == p)continue;
//         if(!voltcentroid[i.to]){
//             c_szamol(i.to, max(mx_w, i.w), d+1, x);
//         }
//     }
// }

// void c_frissit(int x, int mx_w, int d, int p = -1){
//     add(st_ut, d);
//     if(mx_w >= d){
//         add(st_ut_max, min(st_size-1, mx_w-d));
//     }
//     for(edge&i : v[x]){
//         if(i.to == p)continue;
//         if(!voltcentroid[i.to]){
//             c_frissit(i.to, max(mx_w, i.w), d+1, x);
//         }
//     }
// }

struct c_ut {
    int w, x, d;
    bool operator<(const c_ut & other) const {
        return -w < -other.w;
    }
};

void megold(int x = 0){
    int meret = c_szamoz(x);
    int centroid = c_keres(x, meret);

    st_ut.assign(st_size*2, 0);
    // st_ut_max.assign(st_size*2, 0);

    add(st_ut, 0);

    vector<bool> seen(n, 0);
    seen[centroid] = 1;
    priority_queue<c_ut> q;
    for(edge&i : v[centroid]){
        if(!voltcentroid[i.to]){
            q.push({i.w, i.to, 1});
        }
    }
    while(!q.empty()){
        c_ut c = q.top();
        q.pop();
        if(seen[c.x])continue;
        seen[c.x] = 1;
        ans += query(st_ut, 0, c.w-c.d-k);
        add(st_ut, c.d);
        for(edge&i : v[c.x]){
            if(!seen[i.to] && !voltcentroid[i.to]){
                q.push({max(c.w, i.w), i.to, c.d+1});
            }
        }
    }

    for(edge&i : v[centroid]){
        if(!voltcentroid[i.to]){
            st_ut.assign(st_size*2, 0);
            // add(st_ut, 0);
            seen.assign(n, 0);
            seen[centroid] = 1;
            priority_queue<c_ut> q;
            q.push({i.w, i.to, 1});
            while(!q.empty()){
                c_ut c = q.top();
                q.pop();
                if(seen[c.x])continue;
                seen[c.x] = 1;
                ans -= query(st_ut, 0, c.w-c.d-k);
                add(st_ut, c.d);
                for(edge&i : v[c.x]){
                    if(!seen[i.to] && !voltcentroid[i.to]){
                        q.push({max(c.w, i.w), i.to, c.d+1});
                    }
                }
            }

        }
    }


    // add(st_ut, 0);

    // for(edge&i : v[centroid]){
    //     if(!voltcentroid[i.to]){
    //         c_szamol(i.to, i.w, 1, centroid);
    //         c_frissit(i.to, i.w, 1, centroid);
    //     }
    // }


    voltcentroid[centroid] = true;
    for(edge&i : v[centroid]){
        if(!voltcentroid[i.to]){
            megold(i.to);
        }
    }
}

void solve(){
    cin>>n>>k;
    v.assign(n, {});
    voltcentroid.assign(n, 0);
    siz.assign(n, 0);
    for(int i = 0; i < n-1; i++){
        int a, b, c; cin>>a>>b>>c; a--; b--;
        v[a].push_back({b, c});
        v[b].push_back({a, c});
    }
    megold();
    cout<<ans*2<<endl;
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    int _t = 1;
#ifdef MULTI_TEST_CASE
    cin >> _t;
#endif
    for(int _i = 0; _i < _t; _i++){
        #ifdef TEST_TEXT
        cout<<"Case #"<<_i+1<<": ";
        #endif
        solve();
    }
    return 0;
}

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 4436 KB Output is correct
2 Correct 3 ms 4436 KB Output is correct
3 Correct 45 ms 4436 KB Output is correct
4 Correct 446 ms 4564 KB Output is correct
5 Correct 451 ms 4564 KB Output is correct
6 Correct 383 ms 4564 KB Output is correct
7 Correct 401 ms 4564 KB Output is correct
8 Correct 385 ms 4676 KB Output is correct
9 Correct 428 ms 4512 KB Output is correct
10 Correct 390 ms 4512 KB Output is correct
11 Correct 397 ms 4508 KB Output is correct
12 Correct 381 ms 4504 KB Output is correct
13 Correct 383 ms 4504 KB Output is correct
14 Correct 403 ms 4504 KB Output is correct
15 Correct 389 ms 4496 KB Output is correct
16 Correct 381 ms 4508 KB Output is correct
17 Correct 390 ms 4436 KB Output is correct
18 Correct 378 ms 4520 KB Output is correct
19 Correct 379 ms 4504 KB Output is correct
20 Correct 381 ms 4504 KB Output is correct
21 Correct 393 ms 4436 KB Output is correct
22 Correct 402 ms 4516 KB Output is correct

Subtask #2
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 4436 KB Output is correct
2 Correct 3 ms 4436 KB Output is correct
3 Correct 47 ms 4440 KB Output is correct
4 Correct 391 ms 4564 KB Output is correct
5 Execution timed out 1559 ms 5716 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 60.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 4436 KB Output is correct
2 Correct 3 ms 4436 KB Output is correct
3 Correct 45 ms 4436 KB Output is correct
4 Correct 446 ms 4564 KB Output is correct
5 Correct 451 ms 4564 KB Output is correct
6 Correct 383 ms 4564 KB Output is correct
7 Correct 401 ms 4564 KB Output is correct
8 Correct 385 ms 4676 KB Output is correct
9 Correct 428 ms 4512 KB Output is correct
10 Correct 390 ms 4512 KB Output is correct
11 Correct 397 ms 4508 KB Output is correct
12 Correct 381 ms 4504 KB Output is correct
13 Correct 383 ms 4504 KB Output is correct
14 Correct 403 ms 4504 KB Output is correct
15 Correct 389 ms 4496 KB Output is correct
16 Correct 381 ms 4508 KB Output is correct
17 Correct 390 ms 4436 KB Output is correct
18 Correct 378 ms 4520 KB Output is correct
19 Correct 379 ms 4504 KB Output is correct
20 Correct 381 ms 4504 KB Output is correct
21 Correct 393 ms 4436 KB Output is correct
22 Correct 402 ms 4516 KB Output is correct
23 Correct 2 ms 4436 KB Output is correct
24 Correct 3 ms 4436 KB Output is correct
25 Correct 47 ms 4440 KB Output is correct
26 Correct 391 ms 4564 KB Output is correct
27 Execution timed out 1559 ms 5716 KB Time limit exceeded
28 Halted 0 ms 0 KB -