oj.uz

Submission #955933

# Submission time Handle Problem Language Result Execution time Memory
955933 2024-03-31T17:40:44 Z dosts Parkovi (COCI22_parkovi) C++17
30 / 110
 3000 ms 32516 KB 
//Dost SEFEROĞLU
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define F(xxx,yyy) for (int xxx=0;xxx<yyy;xxx++)
#define pii pair<int,int>
#define ff first
#define ss second
#define sp << " " << 
#define vi vector<int>
const int N = 2e5+1,inf = 2e18,MOD = 1e9+7;

vector<pii> edges[N];
vi d(N),p(N);

void dfs(int node,int pp,int dd=0) {
    d[node] = dd;
    p[node] = pp;
    for (auto it : edges[node]) {
        if (it.ff == pp) continue;
        dfs(it.ff,node,dd+it.second);
    }
}

void solve() {
    int n,k;
    cin >> n >> k;
    for (int i=1;i<=n;i++) {
        int a,b,c;
        cin >> a >> b >> c;
        edges[a].push_back({b,c});
        edges[b].push_back({a,c});
    }
    dfs(1,1);
    vi order(n+1);
    for (int i=1;i<=n;i++) order[i] = i;
    sort(order.begin()+1,order.end(),[&](int x,int y) {
        return d[x] > d[y];
    });
    vi done(n+1);
    auto f = [&](int x,bool debug = 0) {
        done.assign(n+1,0);
        int ans = 0;
        for (int i=1;i<=n;i++) {
            int nd = order[i];
            if (done[nd]) continue;
            ans++;
            int cur = nd;
            int curdist = 0;
            while (curdist <= x && cur != 1) {
                if (curdist+(d[cur]-d[p[cur]]) <= x) {
                    curdist+=(d[cur]-d[p[cur]]);
                    cur = p[cur];
                } else break;
            }
            if (debug) cout << nd sp cur << endl;
            queue<pii> q;
            q.push({cur,0});
            done[cur] = 2;
            while (!q.empty()) {
                pii f = q.front();
                q.pop();
                for (auto it : edges[f.ff]) {
                    if (done[it.ff]) continue;
                    if (f.ss+it.ss > x) continue;
                    done[it.ff] = 1;
                    q.push({it.ff,it.ss+f.ss});
                }
            }
        }
        if (debug) cout << endl;
        return ans;
    };
    //f(8,1);
    int l = 0;
    int r = 1e18;
    while (l<=r) {
        int m = (l+r) >> 1;
        int x = f(m);
        //cout << "TRY : " << m sp "gives" sp x<< endl;
        if (x <= k) r = m-1;
        else l = m+1;
    }
    f(l);
    cout << l << endl;
    for (int i=1;i<=n;i++) {
        if (done[i] == 2) {
            k--;
            cout << i;
            if (k) cout << " ";
        }
    }
    if (k) {
        for (int i=1;i<=n;i++) {
            if (k && done[i] != 2) {
                k--;
                cout << i << " ";
            }
        }
        cout << endl;
    }
    else cout << endl;
}
                 
                             
signed main() { 
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    #ifdef Dodi
        freopen("in.txt","r",stdin);
        freopen("out.txt","w",stdout);
    #endif
    int t = 1;
    //cin >> t; 
    while (t --> 0) solve();
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8280 KB Output is correct
2 Correct 3 ms 8284 KB Output is correct
3 Correct 4 ms 8284 KB Output is correct
4 Correct 3 ms 8284 KB Output is correct
5 Correct 3 ms 8280 KB Output is correct
6 Correct 3 ms 8284 KB Output is correct
7 Incorrect 4 ms 8284 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 208 ms 29700 KB Output is correct
2 Correct 190 ms 31568 KB Output is correct
3 Correct 359 ms 29048 KB Output is correct
4 Correct 782 ms 25632 KB Output is correct
5 Correct 705 ms 24868 KB Output is correct
6 Correct 605 ms 24860 KB Output is correct
7 Correct 790 ms 23600 KB Output is correct
8 Correct 707 ms 24432 KB Output is correct
9 Correct 713 ms 24660 KB Output is correct
10 Correct 786 ms 25200 KB Output is correct
11 Correct 2145 ms 25648 KB Output is correct
12 Correct 2451 ms 25228 KB Output is correct
13 Correct 1878 ms 26792 KB Output is correct
14 Correct 2308 ms 23800 KB Output is correct
15 Execution timed out 3045 ms 23512 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 205 ms 32088 KB Output is correct
2 Correct 190 ms 31416 KB Output is correct
3 Correct 184 ms 30192 KB Output is correct
4 Correct 184 ms 30180 KB Output is correct
5 Correct 324 ms 32012 KB Output is correct
6 Correct 333 ms 31792 KB Output is correct
7 Correct 321 ms 32516 KB Output is correct
8 Correct 193 ms 31316 KB Output is correct
9 Correct 196 ms 31132 KB Output is correct
10 Correct 198 ms 31004 KB Output is correct
11 Correct 180 ms 30032 KB Output is correct
12 Correct 328 ms 32340 KB Output is correct
13 Correct 360 ms 32264 KB Output is correct
14 Correct 313 ms 31748 KB Output is correct
15 Correct 215 ms 30148 KB Output is correct
16 Correct 203 ms 29008 KB Output is correct
17 Correct 203 ms 29012 KB Output is correct
18 Correct 227 ms 30292 KB Output is correct
19 Correct 238 ms 30288 KB Output is correct
20 Correct 247 ms 30604 KB Output is correct
21 Correct 260 ms 30008 KB Output is correct

Subtask #4
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8280 KB Output is correct
2 Correct 3 ms 8284 KB Output is correct
3 Correct 4 ms 8284 KB Output is correct
4 Correct 3 ms 8284 KB Output is correct
5 Correct 3 ms 8280 KB Output is correct
6 Correct 3 ms 8284 KB Output is correct
7 Incorrect 4 ms 8284 KB Output isn't correct
8 Halted 0 ms 0 KB -