oj.uz

Submission #839575

# Submission time Handle Problem Language Result Execution time Memory
839575 2023-08-30T09:00:03 Z model_code Truck Driver (IOI23_deliveries) C++17
8 / 100
 103 ms 7712 KB 
// incorrect/sol_vp_fixed_guess.cpp

#include "deliveries.h"
#include <algorithm>
#include <vector>
#include <iostream>
#include <queue>

using namespace std;

vector<vector<pair<int, long long>>> g;
vector<long long> dist;
vector<int> cnt;
vector<bool> vis;
priority_queue<pair<int, int>> pq;


long long weight_sum = 0;
int C;

long long dfs(int x, long long d){
    vis[x] = true;
    dist[x] = d;
    long long res = cnt[x];
    for(auto [y, w] : g[x]){
        if(!vis[y]){
            long long tmp = dfs(y, w + d);
            weight_sum += w * tmp;
            res += tmp;
        }
    }
    return res;
}

void update(int x, int c){
    int tmp = cnt[x];
    cnt[x] = c;
    pq.push({cnt[x], x});
    while(cnt[pq.top().second] != pq.top().first) pq.pop();
    if(pq.top().second != C){
        C = pq.top().second;
        weight_sum = 0;
        vis.assign(g.size(), false);
        dfs(C, 0);
    } else {
        weight_sum += (c - tmp) * dist[x];
    }
}

void init(int N, std::vector<int> U, std::vector<int> V, std::vector<int> T, std::vector<int> W) {
	g.resize(N);
    dist.assign(N, 0);
    cnt = W;
    cnt[0]++;
    for(int i = 0; i < N-1; i++){
        g[U[i]].emplace_back(V[i], T[i]);
        g[V[i]].emplace_back(U[i], T[i]);
    }

    for(int i = 0; i < N; i++){
        pq.push({cnt[i], i});
    }

    weight_sum = 0;
    vis.assign(N, false);
    dfs(0, 0);

    return;
}

long long max_time(int S, int X) {
    if(S == 0) X++;
	update(S, X);
    // cout << "centroid: " << C << endl;

    return weight_sum * 2;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 7620 KB Output is correct
2 Correct 99 ms 7500 KB Output is correct
3 Correct 97 ms 7712 KB Output is correct
4 Correct 98 ms 7572 KB Output is correct
5 Correct 103 ms 7708 KB Output is correct

Subtask #2
0.0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB 6th lines differ - on the 1st token, expected: '953604', found: '1558512'
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 7620 KB Output is correct
2 Correct 99 ms 7500 KB Output is correct
3 Correct 97 ms 7712 KB Output is correct
4 Correct 98 ms 7572 KB Output is correct
5 Correct 103 ms 7708 KB Output is correct
6 Incorrect 1 ms 212 KB 4th lines differ - on the 1st token, expected: '94430', found: '95166'
7 Halted 0 ms 0 KB -

Subtask #4
0.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 7620 KB Output is correct
2 Correct 99 ms 7500 KB Output is correct
3 Correct 97 ms 7712 KB Output is correct
4 Correct 98 ms 7572 KB Output is correct
5 Correct 103 ms 7708 KB Output is correct
6 Incorrect 1 ms 212 KB 4th lines differ - on the 1st token, expected: '124634', found: '268582'
7 Halted 0 ms 0 KB -

Subtask #5
0.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 7620 KB Output is correct
2 Correct 99 ms 7500 KB Output is correct
3 Correct 97 ms 7712 KB Output is correct
4 Correct 98 ms 7572 KB Output is correct
5 Correct 103 ms 7708 KB Output is correct
6 Incorrect 1 ms 340 KB 6th lines differ - on the 1st token, expected: '953604', found: '1558512'
7 Halted 0 ms 0 KB -