oj.uz

Submission #880621

# Submission time Handle Problem Language Result Execution time Memory
880621 2023-11-29T18:06:38 Z tsumondai Parkovi (COCI22_parkovi) C++14
10 / 110
 784 ms 38508 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define foru(i, l, r) for(int i = l; i <= r; i++)
#define ford(i, r, l) for(int i = r; i >= l; i--)
#define __TIME  (1.0 * clock() / CLOCKS_PER_SEC)

typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;
 
const int N = 2e5 + 5;
 
const int oo = 1e18, mod = 1e9 + 7;
 
int n, m, k, mid, uk, flag[N], marked[N];
vector<ii> adj[N];
vector<int> res;


int dfs(int x, int par) {
    if (adj[x].size() == 1 && x != 0) return 0;
    int mi = (1ll << 60), ma = -(1ll << 60);
    for (auto tr : adj[x]) {
        int y = tr.fi;
        int d = tr.se;
        if (y == par) continue;
        int a = dfs(y, x);
        if (a == 0 && flag[y] == 1) {
            mi = min(mi, 0ll);
            ma = max(ma, 0ll);
            continue;
        }
        if (a < 0 && a + d <= 0) flag[x] = 1;

        if (a < 0 && a + d > 0) a = 0;
        else a += d;

        if (a > mid) {
            uk++;
            marked[y] = 1;
            a = min(-mid + d, 0ll);
            if (-mid + d <= 0) flag[x] = 1;
            flag[y] = 1;
        }


        ma = max(ma, a);
        mi = min(mi, a);
    }
    if (-mi >= ma) {
        return mi;
    }
    return ma;
}


int binary_search(int lo, int hi) {
    while (lo < hi) {
        mid = lo + (hi-lo)/2;
        uk=0;
        memset(flag, 0, sizeof(flag));
        memset(marked, 0, sizeof(marked));
        if (dfs(0,0)>0 || flag[0]==0) marked[0]=1, uk++;

        if (uk<=k)
            hi = mid;
        else
            lo = mid+1;
    }
   	return lo; 
}


void process() {
	res.clear();
	cin >> n >> k;
	foru(i,1,n-1) {
		int u, v, w; cin >> u >> v >> w;
		u--, v--;
		adj[u].pb({v,w});
		adj[v].pb({u,w});
	}
	/*mid=binary_search(0, oo);
	uk=0;
	cout << mid << '\n';
	memset(flag, 0, sizeof(flag));
	memset(marked, 0, sizeof(marked));
	if (dfs(0,0)>0 || flag[0]==0) marked[0]=1, uk++;
	foru(i,1,n) if (marked[i]==1) res.pb(i);
	foru(i,1,n) if (res.size()<k && marked[i]==0) res.pb(i);
	for (auto x: res) cout << x << ' ';*/

	int lo = 0, hi = (1LL << 60);
    while (lo < hi) {
        mid = (lo + hi) / 2;
        uk = 0;
        memset(flag, 0, sizeof flag);
        memset(marked, 0, sizeof marked);
        if (dfs(0, 0) > 0) marked[0] = 1, uk++;
        else if (flag[0] == 0) marked[0] = 1, uk++;

        //cout << endl << uk << endl;
        //cout << mid << " " << uk << endl;

        if (uk <= k) hi = mid;
        else         lo = mid + 1;
    }

    mid = lo;
    uk = 0;
    memset(flag, 0, sizeof flag);
    memset(marked, 0, sizeof marked);
    if (dfs(0, 0) > 0) marked[0] = 1, uk++;
    else if (flag[0] == 0) marked[0] = 1, uk++;

    cout << lo << "\n";
    vector <int> out;
    foru(i,1,n) if (marked[i] == 1) out.push_back(i + 1);
    foru(i,1,n) if (out.size() < k && marked[i] == 0) out.push_back(i + 1);
    for (int x : out) cout << x << " "; cout << "\n";

}

signed main() {
    cin.tie(0)->sync_with_stdio(false);
    //freopen(".inp", "r", stdin);
    //freopen(".out", "w", stdout);
    process();
    cerr << "Time elapsed: " << __TIME << " s.\n";
    return 0;
}

/*
Xét các trường hợp đặc biệt
Kiểm tra lại input/output
Cố gắng trâu
Lật ngược bài toán
Keep calm and get VOI 
Flow:

*/

Compilation message

Main.cpp: In function 'void process()':
Main.cpp:125:32: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
  125 |     foru(i,1,n) if (out.size() < k && marked[i] == 0) out.push_back(i + 1);
      |                     ~~~~~~~~~~~^~~
Main.cpp:126:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  126 |     for (int x : out) cout << x << " "; cout << "\n";
      |     ^~~
Main.cpp:126:41: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  126 |     for (int x : out) cout << x << " "; cout << "\n";
      |                                         ^~~~

Subtask #1
0 / 10.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 280 ms 31684 KB Output is correct
2 Correct 327 ms 36656 KB Output is correct
3 Correct 197 ms 22280 KB Output is correct
4 Correct 634 ms 21852 KB Output is correct
5 Correct 784 ms 21592 KB Output is correct
6 Correct 737 ms 21608 KB Output is correct
7 Correct 730 ms 20408 KB Output is correct
8 Correct 784 ms 21060 KB Output is correct
9 Correct 646 ms 21328 KB Output is correct
10 Correct 756 ms 21768 KB Output is correct
11 Correct 604 ms 23168 KB Output is correct
12 Correct 540 ms 23124 KB Output is correct
13 Correct 699 ms 24916 KB Output is correct
14 Correct 648 ms 22084 KB Output is correct
15 Correct 613 ms 21472 KB Output is correct
16 Correct 699 ms 22848 KB Output is correct
17 Correct 511 ms 21976 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 323 ms 32596 KB Output is correct
2 Correct 346 ms 36432 KB Output is correct
3 Correct 314 ms 34912 KB Output is correct
4 Correct 295 ms 34856 KB Output is correct
5 Incorrect 331 ms 38508 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 60.0

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