oj.uz

답안 #524202

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
524202 2022-02-08T18:50:09 Z Cross_Ratio Firefighting (NOI20_firefighting) C++14
100 / 100
 276 ms 44328 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int INF = 1e18;
typedef pair<int,int> P;
vector<vector<P>> adj;
bool type[300005];
vector<int> ans;
int K;
int dfs(int c, int p, int len) {
    int ma = 0, mi = INF;
    for(P n2 : adj[c]) {
        int n = n2.first;
        int d = n2.second;
        if(n==p) continue;
        int l = dfs(n, c, d);
        if(type[n]) mi = min(mi, l); // sobang case
        else ma = max(ma, l);
    }
    //cout << c << ' ' <<ma << ' ' << mi << '\n';
    if(mi + ma > K) {
        if(len == -1 || ma + len > K) {
            type[c] = true;
            ans.push_back(c);
            return len;
        }
        type[c] = false;
        return len + ma;
    }
    if(mi+len > K) {
        type[c] = false;
        return 0;
    }
    type[c] = true;
    return len + mi;
}
signed main() {
    cin.sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int N;
    cin >> N >> K;
    int i;
    adj.resize(N);
    for(i=0;i<N-1;i++) {
        int a, b, c;
        cin >> a >> b >>c;
        adj[a-1].push_back(P(b-1, c));
        adj[b-1].push_back(P(a-1, c));
    }
    dfs(0, -1, -1);
    cout << ans.size() << '\n';
    for(i=0;i<ans.size();i++) cout << ans[i] + 1 << ' ';
}

Compilation message

Firefighting.cpp: In function 'int main()':
Firefighting.cpp:53:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |     for(i=0;i<ans.size();i++) cout << ans[i] + 1 << ' ';
      |             ~^~~~~~~~~~~

Subtask #1
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 271 ms 28048 KB Output is correct
2 Correct 255 ms 28076 KB Output is correct
3 Correct 70 ms 10608 KB Output is correct
4 Correct 251 ms 27312 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct

Subtask #2
5.0 / 5.0

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

Subtask #3
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Correct 0 ms 204 KB Output is correct
11 Correct 0 ms 204 KB Output is correct
12 Correct 0 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 0 ms 204 KB Output is correct
15 Correct 0 ms 204 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 0 ms 204 KB Output is correct
21 Correct 0 ms 204 KB Output is correct
22 Correct 1 ms 204 KB Output is correct
23 Correct 0 ms 204 KB Output is correct
24 Correct 1 ms 204 KB Output is correct
25 Correct 1 ms 204 KB Output is correct
26 Correct 1 ms 204 KB Output is correct

Subtask #4
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 263 ms 28020 KB Output is correct
2 Correct 116 ms 14788 KB Output is correct
3 Correct 156 ms 15128 KB Output is correct
4 Correct 96 ms 13220 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 188 ms 26452 KB Output is correct
8 Correct 190 ms 26492 KB Output is correct
9 Correct 187 ms 26428 KB Output is correct
10 Correct 190 ms 26496 KB Output is correct
11 Correct 261 ms 28132 KB Output is correct
12 Correct 161 ms 18332 KB Output is correct
13 Correct 80 ms 13460 KB Output is correct
14 Correct 147 ms 20248 KB Output is correct
15 Correct 179 ms 24276 KB Output is correct
16 Correct 199 ms 25664 KB Output is correct
17 Correct 167 ms 22056 KB Output is correct
18 Correct 167 ms 21688 KB Output is correct

Subtask #5
26.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 2 ms 564 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 2 ms 460 KB Output is correct
5 Correct 2 ms 716 KB Output is correct
6 Correct 2 ms 716 KB Output is correct
7 Correct 2 ms 716 KB Output is correct
8 Correct 2 ms 716 KB Output is correct
9 Correct 2 ms 584 KB Output is correct
10 Correct 2 ms 588 KB Output is correct
11 Correct 2 ms 716 KB Output is correct
12 Correct 1 ms 460 KB Output is correct
13 Correct 2 ms 728 KB Output is correct
14 Correct 2 ms 588 KB Output is correct
15 Correct 2 ms 588 KB Output is correct
16 Correct 1 ms 460 KB Output is correct
17 Correct 1 ms 460 KB Output is correct
18 Correct 2 ms 588 KB Output is correct
19 Correct 1 ms 460 KB Output is correct
20 Correct 1 ms 460 KB Output is correct
21 Correct 2 ms 588 KB Output is correct

Subtask #6
38.0 / 38.0

# 결과 실행 시간 메모리 Grader output
1 Correct 233 ms 23036 KB Output is correct
2 Correct 229 ms 24616 KB Output is correct
3 Correct 253 ms 26376 KB Output is correct
4 Correct 104 ms 13808 KB Output is correct
5 Correct 263 ms 39704 KB Output is correct
6 Correct 264 ms 38724 KB Output is correct
7 Correct 267 ms 42996 KB Output is correct
8 Correct 275 ms 41948 KB Output is correct
9 Correct 263 ms 36108 KB Output is correct
10 Correct 273 ms 35336 KB Output is correct
11 Correct 258 ms 44328 KB Output is correct
12 Correct 150 ms 18624 KB Output is correct
13 Correct 262 ms 37188 KB Output is correct
14 Correct 276 ms 33312 KB Output is correct
15 Correct 254 ms 26676 KB Output is correct
16 Correct 237 ms 25220 KB Output is correct
17 Correct 243 ms 24968 KB Output is correct
18 Correct 258 ms 26576 KB Output is correct
19 Correct 158 ms 19276 KB Output is correct
20 Correct 72 ms 12236 KB Output is correct
21 Correct 245 ms 26464 KB Output is correct