oj.uz

Submission #891260

# Submission time Handle Problem Language Result Execution time Memory
891260 2023-12-22T15:42:20 Z Maaxle Closing Time (IOI23_closing) C++17
0 / 100
 355 ms 36904 KB 
#include "closing.h"
#include <bits/stdc++.h>
    
#define range(it, a, b) for (ll it = a; it < b; it++)
#define all(x) begin(x), end(x)
#define ll long long
#define ull unsigned long long
#define INF64 ((ll) 1 << 60)
#define INF32 ((ll) 1 << 30)
#define uset unordered_set
#define umap unordered_map 
#define pqueue priority_queue
    
using namespace std;
    
vector<vector<pair<ll, ll>>> adj;
vector<ll> from_x, from_y;
vector<ll> path_x, path_y;

struct TPos {
    ll i;
};
    
bool operator < (const TPos& a, const TPos& b) {
    return (max(from_x[a.i], from_y[a.i]) < max(from_x[b.i], from_y[b.i]));
}

void dfs_x (ll i, ll cnt, ll from) {
    from_x[i] = cnt;
    path_x[i] = from;
    for (pair<ll, ll> k : adj[i]) {
        if (from_x[k.first] == INF64) {
            dfs_x(k.first, cnt + k.second, i);
        }
    }
}
    
void dfs_y (ll i, ll cnt, ll from) {
    from_y[i] = cnt;
    path_y[i] = from;
    for (pair<ll, ll> k : adj[i]) {
        if (from_y[k.first] == INF64) {
            dfs_y(k.first, cnt + k.second, i);
        }
    }
}
    
int max_score(int N, int X, int Y, long long K, vector<int> U, vector<int> V, vector<int> W) {
    adj.clear();
    adj.resize(N);
    
    from_x.clear();
    from_x.resize(N, INF64);
    
    from_y.clear();
    from_y.resize(N, INF64);

    path_y.clear();
    path_y.resize(N);

    path_x.clear();
    path_x.resize(N);
    
    range(i, 0, N - 1){
        adj[U[i]].push_back({V[i], W[i]});
        adj[V[i]].push_back({U[i], W[i]});
    }
    
    ll ans = 2*N;
    dfs_x(X, 0, X);
    dfs_y(Y, 0, X);
    
    pqueue<TPos> pq;
    vector<ll> memo_x (N), memo_y(N);
    ll sum = 0;
    range(i, 0, N) {
        if (adj[i].size() == 1)
            pq.push({i});
        sum += max(from_x[i], from_y[i]);
    }
    
    while (sum > K) {
        TPos t = pq.top(); pq.pop();
        if (!from_x[t.i] && !from_y[t.i]) continue;
        
        if (from_x[t.i] == from_y[t.i] && memo_y[t.i] == adj[t.i].size() - 1 && memo_x[t.i] == adj[t.i].size() - 1) {
            sum -= from_x[t.i];
            ans -= 2;
            from_x[t.i] = from_y[t.i] = 0;
            memo_x[path_x[t.i]]++;
            memo_y[path_y[t.i]]++;
        }
        else if (from_x[t.i] > from_y[t.i] && memo_x[t.i] == adj[t.i].size() - 1) {
            ll dif = from_x[t.i] - from_y[t.i];
            from_x[t.i] = 0;
            sum -= dif;
            ans--;
            memo_x[path_x[t.i]]++;
            pq.push({path_x[t.i]});
            pq.push(t);
        }
        else if (from_y[t.i] > from_x[t.i] && memo_y[t.i] == adj[t.i].size() - 1) {
            ll dif = from_y[t.i] - from_x[t.i];
            from_y[t.i] = 0;
            sum -= dif;
            ans--;
            memo_y[path_y[t.i]]++;
            pq.push({path_y[t.i]});
            pq.push(t);
        }
    }
    
    return ans;
}

Compilation message

closing.cpp: In function 'int max_score(int, int, int, long long int, std::vector<int>, std::vector<int>, std::vector<int>)':
closing.cpp:86:55: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |         if (from_x[t.i] == from_y[t.i] && memo_y[t.i] == adj[t.i].size() - 1 && memo_x[t.i] == adj[t.i].size() - 1) {
closing.cpp:86:93: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |         if (from_x[t.i] == from_y[t.i] && memo_y[t.i] == adj[t.i].size() - 1 && memo_x[t.i] == adj[t.i].size() - 1) {
closing.cpp:93:59: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |         else if (from_x[t.i] > from_y[t.i] && memo_x[t.i] == adj[t.i].size() - 1) {
closing.cpp:102:59: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |         else if (from_y[t.i] > from_x[t.i] && memo_y[t.i] == adj[t.i].size() - 1) {

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct

Subtask #1
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 355 ms 36904 KB 1st lines differ - on the 1st token, expected: '451', found: '182'
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Incorrect 0 ms 348 KB 1st lines differ - on the 1st token, expected: '96', found: '93'
7 Halted 0 ms 0 KB -

Subtask #3
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Incorrect 0 ms 348 KB 1st lines differ - on the 1st token, expected: '96', found: '93'
7 Halted 0 ms 0 KB -

Subtask #4
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Incorrect 0 ms 348 KB 1st lines differ - on the 1st token, expected: '96', found: '93'
7 Halted 0 ms 0 KB -

Subtask #5
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Incorrect 0 ms 344 KB 1st lines differ - on the 1st token, expected: '6', found: '5'
8 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Incorrect 0 ms 348 KB 1st lines differ - on the 1st token, expected: '96', found: '93'
8 Halted 0 ms 0 KB -

Subtask #7
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Incorrect 0 ms 348 KB 1st lines differ - on the 1st token, expected: '96', found: '93'
8 Halted 0 ms 0 KB -

Subtask #8
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Incorrect 0 ms 348 KB 1st lines differ - on the 1st token, expected: '96', found: '93'
8 Halted 0 ms 0 KB -

Subtask #9
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Incorrect 0 ms 348 KB 1st lines differ - on the 1st token, expected: '96', found: '93'
8 Halted 0 ms 0 KB -