oj.uz

답안 #770070

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
770070 2023-06-30T18:01:57 Z vjudge1 Paths (RMI21_paths) C++17
48 / 100
 600 ms 28896 KB 
#include <bits/stdc++.h>
#define ve vector
#define vi vector<int>
#define vii vector<ii>
#define ii pair<int,int>
#define fi first
#define se second
#define ll long long
#define INF 1e9+7
#define pb push_back
#define optimise ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template<class T>
using Tree = tree<T, null_type, less<T>, rb_tree_tag,
    tree_order_statistics_node_update>;
const int MOD = 1e9+7;
const int nax = 1e5+5;
const int l = 25;
void readio(){
    #ifndef ONLINE_JUDGE
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif
}
//segment Tree
ll lazy[nax*4];
pair<ll,int> st[nax*4];
ve<pair<ll,int>> leef;
void build(int v, int l, int r){
    if(l == r){
        st[v] = leef[l];
        lazy[v] = 0;
        return;
    }
    int md = (l+r)/2;
    build(v*2,l,md);
    build(v*2+1,md+1,r);
    st[v] = max(st[v*2], st[v*2+1]);
    lazy[v] = 0;
}
void push(int v){
    if(!lazy[v]) return;
    st[v*2].fi += lazy[v];
    st[v*2+1].fi += lazy[v];
    lazy[v*2] += lazy[v];
    lazy[v*2+1] += lazy[v];
    lazy[v] = 0;
}
void update(int v, int l, int r, int i, int j, ll val){
    if(r < i || l > j) return;
    if(i <= l && r <= j){
        st[v].fi += val;
        lazy[v] += val;
        return;
    }
    push(v);
    int md = (l+r)/2;
    update(v*2,l,md,i,j,val);
    update(v*2+1,md+1,r,i,j,val);
    st[v] = max(st[v*2], st[v*2+1]);
}
ve<pair<int,ll>> adj[nax];
bool vis[nax];
ll dep[nax], w[nax];
int up[nax][l+5];
int timer = 0, root, tin[nax], tout[nax], cnt = 0, tstin[nax], tstout[nax];
void dfs(int u, int p, ll path){
    tin[u] = ++timer;
    tstin[u] = cnt;
    up[u][0] = p;
    for (int i = 1; i <= l; ++i)
        up[u][i] = up[up[u][i-1]][i-1];
    for(auto x : adj[u]){
        if(x.fi == p) continue;
        dep[x.fi] = dep[u]+x.se;
        w[x.fi] = x.se;
        dfs(x.fi,u,path+x.se);
    }
    if(adj[u].size() == 1 && u!=root){
        leef.pb({path, u});
        cnt++;
    }
    tstout[u] = cnt;
    tout[u] = ++timer;
}
void ass(int u){
    if(vis[u] || u == root) return;
    update(1, 0, cnt-1, tstin[u],tstout[u]-1, -w[u]);
    vis[u] = 1;
    ass(up[u][0]);
}



// Subtask 5
pair<ll,int> ans;
bool isAnc(int u, int v){
    return (tin[u] <= tin[v] && tout[v] <= tout[u]);
}
int lca(int u, int v)
{
    if (isAnc(u, v))
        return u;
    if (isAnc(v, u))
        return v;
    for (int i = l; i >= 0; --i) {
        if (!isAnc(up[u][i], v))
            u = up[u][i];
    }
    return up[u][0];
}
ll distance(int a, int b){
    int c = lca(a,b);
    //cout << a << " " << dep[a] << " " << b << " " << dep[b] << endl;
    return (dep[a]+dep[b]-2*dep[c]);
}
void diam(int u, int p, ll cur){
    if(ans.fi < cur) ans.fi = cur, ans.se = u;
    for(auto x : adj[u]){
        if(x.fi == p) continue;
        diam(x.fi, u, cur+x.se);
    }
}




int main()
{
    optimise;
    int n, k;
    cin >> n >> k;
    for(int i = 0; i < n-1; i++){
        int a,b,c;
        cin >> a >> b >> c;
        a--,b--;
        adj[a].pb({b,c});
        adj[b].pb({a,c});
    } 
    if(k == 1){
        dfs(0,0,0);
        int a,b;
        ans = {0,0};
        diam(0,0,0);
        a = ans.se;
        ans = {0,0};
        diam(a,a,0);
        b = ans.se;
        for (int i = 0; i < n; ++i)
        {
            cout << max(distance(a,i), distance(b,i)) << endl;
        }
        return 0;
    }
    for (int i = 0; i < n; ++i)
    {
        memset(vis,0,sizeof vis);
        ll mx = 0;
        root = i;
        cnt = 0;
        timer = 0;
        leef.clear();
        dfs(i,i,0);
        build(1,0,cnt-1);
        //for(auto x : leef) cout << x.fi << " " << x.se << endl;
        //cout << cnt << endl;
        for (int j = 0; j < k; ++j)
        {
            pair<ll,int> a = st[1];
            //cout <<'\t' << a.fi << " " << a.se  << endl;
            mx += a.fi;
            ass(a.se);
        }
        cout << mx << endl;
    }
    
}

Compilation message

Main.cpp: In function 'void readio()':
Main.cpp:23:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |         freopen("input.txt", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:24:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 |         freopen("output.txt", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2772 KB Output is correct
2 Correct 2 ms 2772 KB Output is correct

Subtask #2
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2772 KB Output is correct
2 Correct 2 ms 2772 KB Output is correct
3 Correct 8 ms 2812 KB Output is correct
4 Correct 9 ms 2772 KB Output is correct
5 Correct 7 ms 2772 KB Output is correct
6 Correct 8 ms 2820 KB Output is correct
7 Correct 9 ms 2816 KB Output is correct

Subtask #3
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2772 KB Output is correct
2 Correct 2 ms 2772 KB Output is correct
3 Correct 8 ms 2812 KB Output is correct
4 Correct 9 ms 2772 KB Output is correct
5 Correct 7 ms 2772 KB Output is correct
6 Correct 8 ms 2820 KB Output is correct
7 Correct 9 ms 2816 KB Output is correct
8 Correct 184 ms 3080 KB Output is correct
9 Correct 217 ms 3028 KB Output is correct
10 Correct 172 ms 3028 KB Output is correct
11 Correct 149 ms 3104 KB Output is correct
12 Correct 168 ms 3076 KB Output is correct

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2772 KB Output is correct
2 Correct 2 ms 2772 KB Output is correct
3 Correct 8 ms 2812 KB Output is correct
4 Correct 9 ms 2772 KB Output is correct
5 Correct 7 ms 2772 KB Output is correct
6 Correct 8 ms 2820 KB Output is correct
7 Correct 9 ms 2816 KB Output is correct
8 Correct 184 ms 3080 KB Output is correct
9 Correct 217 ms 3028 KB Output is correct
10 Correct 172 ms 3028 KB Output is correct
11 Correct 149 ms 3104 KB Output is correct
12 Correct 168 ms 3076 KB Output is correct
13 Execution timed out 1038 ms 3396 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #5
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 195 ms 24772 KB Output is correct
2 Correct 217 ms 28896 KB Output is correct
3 Correct 188 ms 26032 KB Output is correct
4 Correct 198 ms 26680 KB Output is correct
5 Correct 217 ms 27688 KB Output is correct
6 Correct 210 ms 26704 KB Output is correct

Subtask #6
0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2772 KB Output is correct
2 Correct 2 ms 2772 KB Output is correct
3 Correct 8 ms 2812 KB Output is correct
4 Correct 9 ms 2772 KB Output is correct
5 Correct 7 ms 2772 KB Output is correct
6 Correct 8 ms 2820 KB Output is correct
7 Correct 9 ms 2816 KB Output is correct
8 Correct 184 ms 3080 KB Output is correct
9 Correct 217 ms 3028 KB Output is correct
10 Correct 172 ms 3028 KB Output is correct
11 Correct 149 ms 3104 KB Output is correct
12 Correct 168 ms 3076 KB Output is correct
13 Execution timed out 1038 ms 3396 KB Time limit exceeded
14 Halted 0 ms 0 KB -