oj.uz

답안 #842876

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
842876 2023-09-03T12:46:31 Z helloworld1705 봉쇄 시간 (IOI23_closing) C++17
8 / 100
 137 ms 78272 KB 
#include "closing.h"
#include <bits/stdc++.h>
using namespace std;
// #define int long long  
 
const int N = 2e6 + 5;
 
long long dx[N] , dy[N];
 
vector <pair <int , long long>> adj[N];
vector <long long> vec = {};
 
void dfs_x(int u , int par) {
    for(auto x : adj[u]) {
       	int v = x.first;
       	long long w = x.second;
        if(v == par) {
            continue;
        }
        dx[v] = dx[u] + w;
        dfs_x(v , u);
    }
}
 
void dfs_y(int u , int par) {
    for(auto x : adj[u]) {
        int v = x.first;
       	long long w = x.second;
        if(v == par) {
            continue;
        }
        dy[v] = dy[u] + w;
        dfs_y(v , u);
    }
}
 
int max_score(int N , int X , int Y , long long K, vector <int> U , vector <int> V , vector <int> W) {
    long long sz = U.size();
    for(long long i = 0; i < sz; i++) {
        adj[U[i]].emplace_back(V[i] , W[i]);
        adj[V[i]].emplace_back(U[i] , W[i]);
    }
    dfs_x(X , X);
    dfs_y(Y , Y);
    for(int i = 0; i < N; i++) {
        vec.push_back(dx[i]);
        vec.push_back(dy[i]);
    }
    sort(vec.begin() , vec.end());
    long long ans = 0;
    long long sum = 0;
    for(int x : vec) {
        sum += x;
        if(sum > K) break;
        ans++;
    }
    vec.clear();
    for(int i = 0; i < N; i++) {
    	adj[i].clear();
    	dx[i] = dy[i] = 0;
    }
    return ans;
}
 
// main() {
 
// 	ios_base::sync_with_stdio(0);
// 	cin.tie(0);	cout.tie(0);
 
// 	int n , x , y , k;
//     cin >> n >> x >> y >> k;
//     vector <int> u(n) , v(n) , w(n);
 
//     for(int i = 0; i < n - 1; i++) {
//     	cin >> u[i];
//     }
//     for(int i = 0; i < n - 1; i++) cin >> v[i];
//     for(int i = 0; i < n - 1; i++) cin >> w[i];
 
//     cout << max_score(n , x , y , k , u , v , w) << '\n';
// }
 
/*
7 0 2 10
0 0 1 2 2 5
1 3 2 4 5 6
2 3 4 2 5 3
*/
 
/*
4 0 3 20
0 1 2
1 2 3
18 1 19
*/

Subtask #0
0.0 / 0.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 10 ms 47704 KB 1st lines differ - on the 1st token, expected: '6', found: '5'
2 Halted 0 ms 0 KB -

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 130 ms 74636 KB Output is correct
2 Correct 137 ms 78272 KB Output is correct
3 Correct 72 ms 50376 KB Output is correct

Subtask #2
0.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 47704 KB Output is correct
2 Incorrect 10 ms 47704 KB 1st lines differ - on the 1st token, expected: '30', found: '24'
3 Halted 0 ms 0 KB -

Subtask #3
0.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 47704 KB Output is correct
2 Incorrect 10 ms 47704 KB 1st lines differ - on the 1st token, expected: '30', found: '24'
3 Halted 0 ms 0 KB -

Subtask #4
0.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 47704 KB Output is correct
2 Incorrect 10 ms 47704 KB 1st lines differ - on the 1st token, expected: '30', found: '24'
3 Halted 0 ms 0 KB -

Subtask #5
0.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 10 ms 47704 KB 1st lines differ - on the 1st token, expected: '6', found: '5'
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 10 ms 47704 KB 1st lines differ - on the 1st token, expected: '6', found: '5'
2 Halted 0 ms 0 KB -

Subtask #7
0.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 10 ms 47704 KB 1st lines differ - on the 1st token, expected: '6', found: '5'
2 Halted 0 ms 0 KB -

Subtask #8
0.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 10 ms 47704 KB 1st lines differ - on the 1st token, expected: '6', found: '5'
2 Halted 0 ms 0 KB -

Subtask #9
0.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 10 ms 47704 KB 1st lines differ - on the 1st token, expected: '6', found: '5'
2 Halted 0 ms 0 KB -