oj.uz

Submission #916806

# Submission time Handle Problem Language Result Execution time Memory
916806 2024-01-26T14:40:16 Z Yang8on Two Currencies (JOI23_currencies) C++17
10 / 100
 4062 ms 757396 KB 
#include <bits/stdc++.h>
#define nosg "Two Currencies"
#define fi(i, a, b) for(int i = a; i <= b; i++)
#define fid(i, a, b) for(int i = a; i >= b; i--)
#define ll long long
#define maxn 6000005
#define gb(i, j) ((i >> j) & 1)
#define pii pair<int, int>
#define f first
#define s second

using namespace std;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

ll GetRandom(ll l, ll r)
{
    return uniform_int_distribution<ll> (l, r) (rng);
}

int n, m, q;
pii edge[maxn], tram[maxn];
vector<int> o[maxn];

int cnt;
int in[maxn], out[maxn];
int h[maxn], cha[maxn][20];

void dfs(int u, int par)
{
    in[u] = ++ cnt;
    for(int v : o[u])
    {
        if(v == par) continue;
        h[v] = h[u] + 1;
        cha[v][0] = u;
        fi(j, 1, 17) cha[v][j] = cha[cha[v][j - 1]][j - 1];
        dfs(v, u);
    }
    out[u] = cnt;
}

int lca(int u, int v)
{
    if(h[u] < h[v]) swap(u, v);
    int kc = h[u] - h[v];
    fi(j, 0, 17) if(gb(kc, j)) u = cha[u][j];
    if(u == v) return u;
    fid(j, 17, 0)
    {
        if(cha[u][j] != cha[v][j])
        {
            u = cha[u][j];
            v = cha[v][j];
        }
    }
    return cha[u][0];
}

int nNode;
int ver[maxn], L[maxn], R[maxn];
ll st[maxn], lazy[maxn];
int newleaf(int id, int l, int r, ll val)
{
    int p = ++ nNode;
    L[p] = L[id], R[p] = R[id];
    st[p] = st[id] + 1ll * (r - l + 1) * val;
    lazy[p] = lazy[id] + val;

    return p;
}
void down(int id, int l, int r)
{
    if(lazy[id])
    {
        if(l != r)
        {
            int mid = (l + r) >> 1;
            L[id] = newleaf(L[id], l, mid, lazy[id]);
            R[id] = newleaf(R[id], mid + 1, r, lazy[id]);
        }
    }
    lazy[id] = 0;
}
int newparent(int lef, int rig)
{
    int p = ++ nNode;
    L[p] = lef, R[p] = rig;
    st[p] = st[L[p]] + st[R[p]];
    return p;
}
int update(int oid, int u, int v, ll val, int l = 1, int r = n)
{
    if(v < l || r < u) return oid;
    if(u <= l && r <= v) return newleaf(oid, l, r, val);
    down(oid, l, r);
    int mid = (l + r) >> 1;
    return newparent( update(L[oid], u, v, val, l, mid), update(R[oid], u, v, val, mid + 1, r) );
}
ll get(int id, int i, int l = 1, int r = n)
{
    if(i < l || r < i) return 0;
    if(l == r) return st[id];
    down(id, l, r);
    int mid = (l + r) >> 1;
    return get(L[id], i, l, mid) + get(R[id], i, mid + 1, r);
}


int nNode2;
int ver2[maxn], L2[maxn], R2[maxn];
ll st2[maxn], lazy2[maxn];
int newleaf2(int id, int l, int r, ll val)
{
    int p = ++ nNode2;
    L2[p] = L2[id], R2[p] = R2[id];
    st2[p] = st2[id] + 1ll * (r - l + 1) * val;
    lazy2[p] = lazy2[id] + val;

    return p;
}
void down2(int id, int l, int r)
{
    if(lazy2[id])
    {
        if(l != r)
        {
            int mid = (l + r) >> 1;
            L2[id] = newleaf2(L2[id], l, mid, lazy2[id]);
            R2[id] = newleaf2(R2[id], mid + 1, r, lazy2[id]);
        }
    }
    lazy2[id] = 0;
}
int newparent2(int lef, int rig)
{
    int p = ++ nNode2;
    L2[p] = lef, R2[p] = rig;
    st2[p] = st2[L2[p]] + st2[R2[p]];
    return p;
}
int update2(int oid, int u, int v, int l = 1, int r = n)
{
    if(v < l || r < u) return oid;
    if(u <= l && r <= v) return newleaf2(oid, l, r, 1);
    down2(oid, l, r);
    int mid = (l + r) >> 1;
    return newparent2( update2(L2[oid], u, v, l, mid), update2(R2[oid], u, v, mid + 1, r) );
}
ll get2(int id, int i, int l = 1, int r = n)
{
    if(i < l || r < i) return 0;
    if(l == r) return st2[id];
    down2(id, l, r);
    int mid = (l + r) >> 1;
    return get2(L2[id], i, l, mid) + get2(R2[id], i, mid + 1, r);
}

int main()
{
//    freopen(nosg".inp","r",stdin);
//    freopen(nosg".out","w",stdout);

    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n >> m >> q;
    fi(i, 1, n - 1)
    {
        cin >> edge[i].f >> edge[i].s;
        int u = edge[i].f, v = edge[i].s;
        o[u].push_back(v);
        o[v].push_back(u);
    }

    dfs(1, -1);

    fi(i, 1, m) cin >> tram[i].f >> tram[i].s;

    sort(tram + 1, tram + m + 1, [](pii x, pii y) {
            return x.s < y.s;
         });

    fi(i, 1, m)
    {
        int j = tram[i].f, val = tram[i].s;
        int u = edge[j].f, v = edge[j].s;

        if(h[u] > h[v]) swap(u, v);

        ver[i] = update(ver[i - 1], in[v], out[v], 1ll * val);
        ver2[i] = update2(ver2[i - 1], in[v], out[v]);
    }

    fi(i, 1, q)
    {
        int u, v;
        ll S, G;

        cin >> u >> v >> G >> S;

        if(h[u] > h[v]) swap(u, v);
        int par = lca(u, v);

        int l = 1, r = m;
        while(l <= r)
        {
            int mid = (l + r) >> 1;
            if(get(ver[mid], in[v]) + get(ver[mid], in[u]) - 2ll * get(ver[mid], in[par]) <= S) l = mid + 1;
            else r = mid - 1;
        }

        int sum = get2(ver2[m], in[v]) + get2(ver2[m], in[u]) - 2ll * get2(ver2[m], in[par]);
        int use = get2(ver2[r], in[v]) + get2(ver2[r], in[u]) - 2ll * get2(ver2[r], in[par]);

        cout << (G - (sum - use) >= 0 ? G - (sum - use) : -1) << '\n';
    }


    /// ------------------check time!-----------------///
    cerr << "\n" << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 150156 KB Output is correct
2 Correct 43 ms 152148 KB Output is correct
3 Correct 43 ms 152156 KB Output is correct
4 Correct 48 ms 152144 KB Output is correct
5 Correct 50 ms 156644 KB Output is correct
6 Correct 56 ms 156460 KB Output is correct
7 Correct 52 ms 157996 KB Output is correct
8 Correct 56 ms 158548 KB Output is correct
9 Correct 56 ms 160852 KB Output is correct
10 Correct 54 ms 158292 KB Output is correct
11 Correct 56 ms 160712 KB Output is correct
12 Correct 57 ms 160816 KB Output is correct
13 Correct 58 ms 170068 KB Output is correct
14 Correct 60 ms 167864 KB Output is correct
15 Correct 59 ms 167848 KB Output is correct
16 Correct 60 ms 164432 KB Output is correct
17 Correct 59 ms 165200 KB Output is correct
18 Correct 59 ms 165456 KB Output is correct
19 Correct 53 ms 157780 KB Output is correct
20 Correct 52 ms 155768 KB Output is correct
21 Correct 53 ms 155648 KB Output is correct
22 Correct 52 ms 155996 KB Output is correct
23 Correct 52 ms 156496 KB Output is correct
24 Correct 52 ms 155984 KB Output is correct
25 Correct 54 ms 158036 KB Output is correct
26 Correct 53 ms 155988 KB Output is correct
27 Correct 53 ms 156024 KB Output is correct
28 Correct 52 ms 156240 KB Output is correct
29 Correct 50 ms 156288 KB Output is correct
30 Correct 54 ms 156756 KB Output is correct
31 Correct 55 ms 158544 KB Output is correct
32 Correct 53 ms 156240 KB Output is correct
33 Correct 58 ms 170064 KB Output is correct
34 Correct 59 ms 168680 KB Output is correct
35 Correct 59 ms 168656 KB Output is correct

Subtask #2
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 152352 KB Output is correct
2 Correct 54 ms 156752 KB Output is correct
3 Correct 57 ms 158544 KB Output is correct
4 Correct 56 ms 156240 KB Output is correct
5 Correct 2207 ms 307532 KB Output is correct
6 Correct 2969 ms 309272 KB Output is correct
7 Correct 2652 ms 274348 KB Output is correct
8 Correct 1880 ms 266868 KB Output is correct
9 Correct 1878 ms 286288 KB Output is correct
10 Correct 4062 ms 355872 KB Output is correct
11 Correct 3621 ms 346756 KB Output is correct
12 Correct 3464 ms 351252 KB Output is correct
13 Correct 3781 ms 363448 KB Output is correct
14 Correct 3660 ms 346768 KB Output is correct
15 Runtime error 733 ms 757396 KB Execution killed with signal 11
16 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 152280 KB Output is correct
2 Correct 61 ms 170064 KB Output is correct
3 Correct 66 ms 168780 KB Output is correct
4 Correct 61 ms 168784 KB Output is correct
5 Runtime error 692 ms 636936 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 150156 KB Output is correct
2 Correct 43 ms 152148 KB Output is correct
3 Correct 43 ms 152156 KB Output is correct
4 Correct 48 ms 152144 KB Output is correct
5 Correct 50 ms 156644 KB Output is correct
6 Correct 56 ms 156460 KB Output is correct
7 Correct 52 ms 157996 KB Output is correct
8 Correct 56 ms 158548 KB Output is correct
9 Correct 56 ms 160852 KB Output is correct
10 Correct 54 ms 158292 KB Output is correct
11 Correct 56 ms 160712 KB Output is correct
12 Correct 57 ms 160816 KB Output is correct
13 Correct 58 ms 170068 KB Output is correct
14 Correct 60 ms 167864 KB Output is correct
15 Correct 59 ms 167848 KB Output is correct
16 Correct 60 ms 164432 KB Output is correct
17 Correct 59 ms 165200 KB Output is correct
18 Correct 59 ms 165456 KB Output is correct
19 Correct 53 ms 157780 KB Output is correct
20 Correct 52 ms 155768 KB Output is correct
21 Correct 53 ms 155648 KB Output is correct
22 Correct 52 ms 155996 KB Output is correct
23 Correct 52 ms 156496 KB Output is correct
24 Correct 52 ms 155984 KB Output is correct
25 Correct 54 ms 158036 KB Output is correct
26 Correct 53 ms 155988 KB Output is correct
27 Correct 53 ms 156024 KB Output is correct
28 Correct 52 ms 156240 KB Output is correct
29 Correct 50 ms 156288 KB Output is correct
30 Correct 54 ms 156756 KB Output is correct
31 Correct 55 ms 158544 KB Output is correct
32 Correct 53 ms 156240 KB Output is correct
33 Correct 58 ms 170064 KB Output is correct
34 Correct 59 ms 168680 KB Output is correct
35 Correct 59 ms 168656 KB Output is correct
36 Correct 46 ms 152352 KB Output is correct
37 Correct 54 ms 156752 KB Output is correct
38 Correct 57 ms 158544 KB Output is correct
39 Correct 56 ms 156240 KB Output is correct
40 Correct 2207 ms 307532 KB Output is correct
41 Correct 2969 ms 309272 KB Output is correct
42 Correct 2652 ms 274348 KB Output is correct
43 Correct 1880 ms 266868 KB Output is correct
44 Correct 1878 ms 286288 KB Output is correct
45 Correct 4062 ms 355872 KB Output is correct
46 Correct 3621 ms 346756 KB Output is correct
47 Correct 3464 ms 351252 KB Output is correct
48 Correct 3781 ms 363448 KB Output is correct
49 Correct 3660 ms 346768 KB Output is correct
50 Runtime error 733 ms 757396 KB Execution killed with signal 11
51 Halted 0 ms 0 KB -