답안 #545517

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
545517	2022-04-04T17:30:27 Z	mat50013	Parkovi (COCI22_parkovi)	C++11	110 / 110	1122 ms	33112 KB

Main

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
const int NMAX(200005);
const ll MAXX(1e16);
vector<pair<int, int> > G[NMAX];
vector<int> aux;
int n, k, fr[NMAX];
ll dis[NMAX];

inline pair<ll, ll> DFS(int nod, int tata, ll cat, ll dUnd)
{
    pair<ll, ll> sol = {MAXX, -MAXX};
    for(auto it: G[nod])
        if(it.first != tata)
        {
            auto ce = DFS(it.first, nod, cat, it.second);
            if(ce.first != MAXX)
                sol.first = min(sol.first, ce.first + it.second);
            if(ce.second != -MAXX)
                sol.second = max(sol.second, ce.second + it.second);
        }
    if(sol.first > cat && sol.second < 0)
    {
        sol.first = MAXX;
        sol.second = 0;
    }
    if(sol.first != MAXX && sol.second != -MAXX && sol.first + sol.second <= cat)
    {
        sol.second = -MAXX;
        return sol;
    }
    if((sol.second != -MAXX && sol.second + dUnd > cat) || (nod == 1 && sol.second >= 0))
    {
        aux.push_back(nod);
        return {0, -MAXX};
    }
    return sol;
}

inline bool test(ll mij, int nr)
{
    aux.clear();
    DFS(1, -1, mij, 0);
    return ((int)aux.size() <= nr);
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    cin >> n >> k;

    for(int i = 1; i < n; ++i)
    {
        int x, y, c;
        cin >> x >> y >> c;
        G[x].push_back({y, c});
        G[y].push_back({x, c});
    }

    vector<int> sol;
    ll st = 0, dr = 1e16, best = 0;
    while(st <= dr)
    {
        ll mij = st + (dr - st) / 2;
        if(test(mij, k))
        {
            best = mij;
            sol = aux;
            dr = mij - 1;
        }
        else st = mij + 1;
    }

    cout << best << '\n';
    for(auto it: sol)
        fr[it] = 1;
    for(int i = 1; i <= n && (int)sol.size() < k; ++i)
        if(fr[i] == 0)
            sol.push_back(i);
    for(auto it: sol)
        cout << it << ' ';
    return 0;
}

Subtask #1

10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	4948 KB	Output is correct
2	Correct	2 ms	4948 KB	Output is correct
3	Correct	3 ms	4948 KB	Output is correct
4	Correct	3 ms	4948 KB	Output is correct
5	Correct	3 ms	4948 KB	Output is correct
6	Correct	2 ms	4948 KB	Output is correct
7	Correct	3 ms	4948 KB	Output is correct
8	Correct	3 ms	4948 KB	Output is correct
9	Correct	3 ms	4948 KB	Output is correct
10	Correct	3 ms	4948 KB	Output is correct
11	Correct	3 ms	4948 KB	Output is correct
12	Correct	4 ms	4948 KB	Output is correct
13	Correct	2 ms	4948 KB	Output is correct
14	Correct	3 ms	4948 KB	Output is correct

Subtask #2

10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	334 ms	28480 KB	Output is correct
2	Correct	331 ms	29088 KB	Output is correct
3	Correct	218 ms	13616 KB	Output is correct
4	Correct	923 ms	12004 KB	Output is correct
5	Correct	876 ms	11844 KB	Output is correct
6	Correct	826 ms	11764 KB	Output is correct
7	Correct	838 ms	11852 KB	Output is correct
8	Correct	887 ms	12188 KB	Output is correct
9	Correct	872 ms	12016 KB	Output is correct
10	Correct	926 ms	12184 KB	Output is correct
11	Correct	592 ms	13512 KB	Output is correct
12	Correct	563 ms	13800 KB	Output is correct
13	Correct	623 ms	14548 KB	Output is correct
14	Correct	542 ms	13576 KB	Output is correct
15	Correct	548 ms	13108 KB	Output is correct
16	Correct	598 ms	13684 KB	Output is correct
17	Correct	551 ms	13072 KB	Output is correct

Subtask #3

30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	339 ms	29588 KB	Output is correct
2	Correct	354 ms	28848 KB	Output is correct
3	Correct	302 ms	27716 KB	Output is correct
4	Correct	323 ms	27664 KB	Output is correct
5	Correct	351 ms	31932 KB	Output is correct
6	Correct	364 ms	31632 KB	Output is correct
7	Correct	388 ms	32900 KB	Output is correct
8	Correct	355 ms	29776 KB	Output is correct
9	Correct	337 ms	29516 KB	Output is correct
10	Correct	338 ms	28908 KB	Output is correct
11	Correct	312 ms	28140 KB	Output is correct
12	Correct	393 ms	32952 KB	Output is correct
13	Correct	402 ms	33112 KB	Output is correct
14	Correct	368 ms	31552 KB	Output is correct
15	Correct	320 ms	28996 KB	Output is correct
16	Correct	321 ms	28108 KB	Output is correct
17	Correct	310 ms	27900 KB	Output is correct
18	Correct	337 ms	29228 KB	Output is correct
19	Correct	341 ms	31420 KB	Output is correct
20	Correct	338 ms	31540 KB	Output is correct
21	Correct	341 ms	30772 KB	Output is correct

Subtask #4

60.0 / 60.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	4948 KB	Output is correct
2	Correct	2 ms	4948 KB	Output is correct
3	Correct	3 ms	4948 KB	Output is correct
4	Correct	3 ms	4948 KB	Output is correct
5	Correct	3 ms	4948 KB	Output is correct
6	Correct	2 ms	4948 KB	Output is correct
7	Correct	3 ms	4948 KB	Output is correct
8	Correct	3 ms	4948 KB	Output is correct
9	Correct	3 ms	4948 KB	Output is correct
10	Correct	3 ms	4948 KB	Output is correct
11	Correct	3 ms	4948 KB	Output is correct
12	Correct	4 ms	4948 KB	Output is correct
13	Correct	2 ms	4948 KB	Output is correct
14	Correct	3 ms	4948 KB	Output is correct
15	Correct	334 ms	28480 KB	Output is correct
16	Correct	331 ms	29088 KB	Output is correct
17	Correct	218 ms	13616 KB	Output is correct
18	Correct	923 ms	12004 KB	Output is correct
19	Correct	876 ms	11844 KB	Output is correct
20	Correct	826 ms	11764 KB	Output is correct
21	Correct	838 ms	11852 KB	Output is correct
22	Correct	887 ms	12188 KB	Output is correct
23	Correct	872 ms	12016 KB	Output is correct
24	Correct	926 ms	12184 KB	Output is correct
25	Correct	592 ms	13512 KB	Output is correct
26	Correct	563 ms	13800 KB	Output is correct
27	Correct	623 ms	14548 KB	Output is correct
28	Correct	542 ms	13576 KB	Output is correct
29	Correct	548 ms	13108 KB	Output is correct
30	Correct	598 ms	13684 KB	Output is correct
31	Correct	551 ms	13072 KB	Output is correct
32	Correct	339 ms	29588 KB	Output is correct
33	Correct	354 ms	28848 KB	Output is correct
34	Correct	302 ms	27716 KB	Output is correct
35	Correct	323 ms	27664 KB	Output is correct
36	Correct	351 ms	31932 KB	Output is correct
37	Correct	364 ms	31632 KB	Output is correct
38	Correct	388 ms	32900 KB	Output is correct
39	Correct	355 ms	29776 KB	Output is correct
40	Correct	337 ms	29516 KB	Output is correct
41	Correct	338 ms	28908 KB	Output is correct
42	Correct	312 ms	28140 KB	Output is correct
43	Correct	393 ms	32952 KB	Output is correct
44	Correct	402 ms	33112 KB	Output is correct
45	Correct	368 ms	31552 KB	Output is correct
46	Correct	320 ms	28996 KB	Output is correct
47	Correct	321 ms	28108 KB	Output is correct
48	Correct	310 ms	27900 KB	Output is correct
49	Correct	337 ms	29228 KB	Output is correct
50	Correct	341 ms	31420 KB	Output is correct
51	Correct	338 ms	31540 KB	Output is correct
52	Correct	341 ms	30772 KB	Output is correct
53	Correct	897 ms	11952 KB	Output is correct
54	Correct	939 ms	12160 KB	Output is correct
55	Correct	1122 ms	12516 KB	Output is correct
56	Correct	935 ms	13284 KB	Output is correct
57	Correct	937 ms	14384 KB	Output is correct
58	Correct	911 ms	12012 KB	Output is correct
59	Correct	994 ms	17324 KB	Output is correct
60	Correct	964 ms	12448 KB	Output is correct
61	Correct	815 ms	11836 KB	Output is correct
62	Correct	821 ms	14420 KB	Output is correct
63	Correct	971 ms	12368 KB	Output is correct
64	Correct	885 ms	15656 KB	Output is correct
65	Correct	910 ms	12292 KB	Output is correct
66	Correct	898 ms	14328 KB	Output is correct
67	Correct	846 ms	11852 KB	Output is correct
68	Correct	1036 ms	16420 KB	Output is correct
69	Correct	342 ms	29160 KB	Output is correct
70	Correct	317 ms	27824 KB	Output is correct
71	Correct	388 ms	32136 KB	Output is correct
72	Correct	209 ms	13252 KB	Output is correct
73	Correct	208 ms	13076 KB	Output is correct
74	Correct	231 ms	15944 KB	Output is correct
75	Correct	588 ms	14008 KB	Output is correct
76	Correct	641 ms	14320 KB	Output is correct
77	Correct	591 ms	13900 KB	Output is correct
78	Correct	579 ms	15628 KB	Output is correct