oj.uz

답안 #524196

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
524196 2022-02-08T18:41:31 Z Cross_Ratio Firefighting (NOI20_firefighting) C++14
8 / 100
 278 ms 28184 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 == INF) {
        if(len == -1 || ma + len > K) {
            type[c] = true;
            ans.push_back(c);
            return len;
        }
        type[c] = false;
        return len + ma;
    }
    if(mi + ma > K) {
        type[c] = true;
        ans.push_back(c);
        return len;
    }
    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:58: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]
   58 |     for(i=0;i<ans.size();i++) cout << ans[i] + 1 << ' ';
      |             ~^~~~~~~~~~~

Subtask #1
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 278 ms 28088 KB Output is correct
2 Correct 259 ms 28044 KB Output is correct
3 Correct 68 ms 10600 KB Output is correct
4 Correct 251 ms 27292 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 1 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 1 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 1 ms 204 KB Output is correct

Subtask #3
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 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 1 ms 204 KB Output is correct
9 Correct 1 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 1 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 268 KB Output is correct
16 Correct 0 ms 204 KB Output is correct
17 Incorrect 0 ms 204 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 270 ms 28184 KB Output is correct
2 Correct 111 ms 14776 KB Output is correct
3 Correct 115 ms 15152 KB Output is correct
4 Correct 114 ms 13116 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 183 ms 26412 KB Output is correct
8 Correct 189 ms 26552 KB Output is correct
9 Correct 189 ms 26512 KB Output is correct
10 Correct 186 ms 26520 KB Output is correct
11 Correct 262 ms 28084 KB Output is correct
12 Incorrect 144 ms 18320 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 460 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 38.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 230 ms 23052 KB Output isn't correct
2 Halted 0 ms 0 KB -