oj.uz

Submission #922025

# Submission time Handle Problem Language Result Execution time Memory
922025 2024-02-04T18:33:39 Z trMatherz Factories (JOI14_factories) C++17
100 / 100
 4369 ms 355528 KB 
#include "factories.h"
/*
#include <fstream>
std::ifstream cin ("ex.in");
std::ofstream cout ("ex.out");
*/




// includes
#include <cmath> 
#include <set>
#include <map>
#include <queue>
#include <string>
#include <vector>
#include <array>
#include <algorithm>
#include <numeric>
#include <iomanip>
#include <unordered_set>
#include <stack>
#include <ext/pb_ds/assoc_container.hpp>
#include <random>
#include <chrono>



//usings 
using namespace std;
using namespace __gnu_pbds;


// misc
#define ll long long
#define pb push_back
#define pq priority_queue
#define ub upper_bound
#define lb lower_bound
template<typename T, typename U> bool emin(T &a, const U &b){ return b < a ? a = b, true : false; }
template<typename T, typename U> bool emax(T &a, const U &b){ return b > a ? a = b, true : false; }
typedef uint64_t hash_t;

// vectors
#define vi vector<int>
#define vvi vector<vi>
#define vvvi vector<vvi>
#define vpii vector<pair<int, int>>
#define vvpii vector<vector<pair<int, int>>>
#define vppipi vector<pair<int, pair<int, int>>>
#define vl vector<ll>
#define vvl vector<vl>
#define vvvl vector<vvl>
#define vpll vector<pair<ll, ll>>
#define vvpll vector<vpll>
#define vb vector<bool>
#define vvb vector<vb>
#define vs vector<string>
#define sz(x) (int)x.size()
#define rz resize
#define all(x) x.begin(), x.end()


// pairs
#define pii pair<int, int>
#define pll pair<ll, ll>
#define mp make_pair
#define f first
#define s second

// sets
#define si set<int>
#define sl set<ll>
#define ss set<string>
#define in insert
template <class T> using iset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

// maps
#define mii map<int, int>
#define mll map<ll, ll>

// loops
#define FR(x, z, y) for (int x = z; x < y; x++)
#define FRE(x, z, y) FR(x, z, y + 1)
#define F(x, y) FR(x, 0, y)
#define FE(x, y) F(x, y + 1)
#define A(x, y) for(auto &x : y)

int n;
vvpll a;
vb b; vi sz;
vvpll used;
vl node;

int getsz(int x, int p = -1){
    sz[x] = 1;
    A(u, a[x]) if(u.f != p && !b[u.f]) sz[x] += getsz(u.f, x);
    return sz[x];
}

int getc(int x, int z, int p = -1){
    A(u, a[x]) if(u.f != p && !b[u.f] && sz[u.f] * 2 > z) return getc(u.f, z, x);
    return x;
}

void go(int x, int c, ll d, int p = -1){
    used[x].pb({c, d});
    A(u, a[x]) if(u.f != p && !b[u.f]) go(u.f, c, d + u.s, x);
}

void build(int x = 0){
    int c = getc(x, getsz(x));
    b[c] = true;
    A(u, a[c]) if(!b[u.f]) go(u.f, c, u.s);
    A(u, a[c]) if(!b[u.f]) build(u.f);
}

void Init(int N, int A[], int B[], int D[]){
    n = N;
    a = vvpll(n);
    used = vvpll(n);
    sz = vi(n);
    b = vb(n, false);
    node = vl(n, (ll) 1e18);
    F(i, n - 1){
        a[A[i]].pb({B[i], D[i]});
        a[B[i]].pb({A[i], D[i]});
    }
    build();
}
ll an;

void upd(int x){
    A(u, used[x]){
        emin(node[u.f], u.s);
    }
    node[x] = 0;
}
void rev(int x){
    A(u, used[x]){
        node[u.f] = (ll) 1e18;
    }
    node[x] = (ll) 1e18;
}

void get(int x){
    A(u, used[x]){
        emin(an, node[u.f] + u.s);
    }
    emin(an, node[x]);
}

ll Query(int S, int X[], int T, int Y[]){
    an = (ll) 1e18;
    F(i, S) upd(X[i]);
    F(i, T) get(Y[i]);
    F(i, S) rev(X[i]);
    return an;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 16988 KB Output is correct
2 Correct 201 ms 22200 KB Output is correct
3 Correct 217 ms 22476 KB Output is correct
4 Correct 219 ms 22876 KB Output is correct
5 Correct 233 ms 23236 KB Output is correct
6 Correct 144 ms 21644 KB Output is correct
7 Correct 253 ms 22460 KB Output is correct
8 Correct 219 ms 22716 KB Output is correct
9 Correct 240 ms 23120 KB Output is correct
10 Correct 144 ms 21584 KB Output is correct
11 Correct 214 ms 22612 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16984 KB Output is correct
2 Correct 2215 ms 195428 KB Output is correct
3 Correct 3254 ms 256672 KB Output is correct
4 Correct 606 ms 106016 KB Output is correct
5 Correct 3996 ms 355528 KB Output is correct
6 Correct 3465 ms 257060 KB Output is correct
7 Correct 792 ms 72016 KB Output is correct
8 Correct 305 ms 47120 KB Output is correct
9 Correct 895 ms 76812 KB Output is correct
10 Correct 846 ms 72796 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 16988 KB Output is correct
2 Correct 201 ms 22200 KB Output is correct
3 Correct 217 ms 22476 KB Output is correct
4 Correct 219 ms 22876 KB Output is correct
5 Correct 233 ms 23236 KB Output is correct
6 Correct 144 ms 21644 KB Output is correct
7 Correct 253 ms 22460 KB Output is correct
8 Correct 219 ms 22716 KB Output is correct
9 Correct 240 ms 23120 KB Output is correct
10 Correct 144 ms 21584 KB Output is correct
11 Correct 214 ms 22612 KB Output is correct
12 Correct 3 ms 16984 KB Output is correct
13 Correct 2215 ms 195428 KB Output is correct
14 Correct 3254 ms 256672 KB Output is correct
15 Correct 606 ms 106016 KB Output is correct
16 Correct 3996 ms 355528 KB Output is correct
17 Correct 3465 ms 257060 KB Output is correct
18 Correct 792 ms 72016 KB Output is correct
19 Correct 305 ms 47120 KB Output is correct
20 Correct 895 ms 76812 KB Output is correct
21 Correct 846 ms 72796 KB Output is correct
22 Correct 2452 ms 209552 KB Output is correct
23 Correct 2463 ms 216020 KB Output is correct
24 Correct 3814 ms 258476 KB Output is correct
25 Correct 3860 ms 262496 KB Output is correct
26 Correct 3574 ms 260260 KB Output is correct
27 Correct 4369 ms 353068 KB Output is correct
28 Correct 775 ms 111216 KB Output is correct
29 Correct 3737 ms 259100 KB Output is correct
30 Correct 3759 ms 258740 KB Output is correct
31 Correct 3706 ms 258924 KB Output is correct
32 Correct 1135 ms 77352 KB Output is correct
33 Correct 243 ms 47232 KB Output is correct
34 Correct 629 ms 61840 KB Output is correct
35 Correct 580 ms 62804 KB Output is correct
36 Correct 828 ms 70564 KB Output is correct
37 Correct 809 ms 70912 KB Output is correct