oj.uz

답안 #823468

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
823468 2023-08-12T14:43:02 Z SUNWOOOOOOOO Two Currencies (JOI23_currencies) C++17
100 / 100
 1648 ms 55716 KB 
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using pint = pair <int, int>;
const int mxN = 100005, SIZE = 200000;
vector <int> adj[mxN], mid[mxN];
int n, m, q, A[mxN], B[mxN], S[mxN], T[mxN], X[mxN], ans[mxN]; LL Y[mxN];
int tin[2 * mxN], tout[2 * mxN], tcnt = 0, low[mxN], high[mxN], L[mxN];
pint C[mxN];

struct lca {
    int par[20][mxN], dep[mxN];
    void dfs(int now, int p){
        par[0][now] = p;
        for (int chi : adj[now]){
            if (chi == p) continue;
            dep[chi] = dep[now] + 1; 
            dfs(chi, now);
        }
    }
    void init(){
        dfs(1, 1);
        for (int i = 1; i < 20; i++){
            for (int j = 1; j <= n; j++){
                par[i][j] = par[i - 1][par[i - 1][j]];
            }
        }
    }
    int query(int x, int y){
        if (dep[x] < dep[y]) swap(x, y);
        int dif = dep[x] - dep[y];
        for (int i = 0; dif; i++){
            if (dif & 1) x = par[i][x];
            dif /= 2;
        }
        for (int i = 19; i >= 0; i--){
            if (par[i][x] != par[i][y]){
                x = par[i][x], y = par[i][y];
            }
        }
        if (x == y) return x;
        else return par[0][x];
    }
} lca;

struct segtree {
    LL node[8 * mxN];
    void init(){
        memset(node, 0, sizeof node);
    }
    void update(int x, int val){
        for (x += 2 * n; x > 0; x /= 2) node[x] += val;
    }
    LL query(int L, int R){
        LL ret = 0;
        for (L += 2 * n, R += 2 * n; L <= R; L /= 2, R /= 2){
            if (L % 2 == 1) ret += node[L++];
            if (R % 2 == 0) ret += node[R--];
        }
        return ret;
    }
} tree1, tree2;

void euler_tour(int now, int p)
{
    tin[now] = ++tcnt;
    for (int elm : adj[now]){
        if (elm == p) continue;
        euler_tour(elm, now);
    }
    tout[now] = ++tcnt;
}

int main()
{
    scanf("%d %d %d", &n, &m, &q);
    for (int i = 1; i <= n - 1; i++){
        scanf("%d %d", &A[i], &B[i]);
        adj[A[i]].push_back(B[i]);
        adj[B[i]].push_back(A[i]);
    }
    for (int i = 1; i <= m; i++) scanf("%d %d", &C[i].second, &C[i].first);
    for (int i = 1; i <= q; i++) scanf("%d %d %d %lld", &S[i], &T[i], &X[i], &Y[i]);

    lca.init();
    euler_tour(1, 1);
    sort(C + 1, C + m + 1); // {silver no, road no}
    for (int i = 1; i <= q; i++){low[i] = 0, high[i] = m;}
    for (int i = 1; i <= q; i++){
        L[i] = lca.query(S[i], T[i]);
    }
    for (int i = 1; i <= n - 1; i++){
        if (lca.dep[A[i]] < lca.dep[B[i]]) swap(A[i], B[i]);
    }
    memset(ans, -1, sizeof ans);

    while (1){
        tree1.init();
        tree2.init();
        for (int i = 0; i <= m; i++) mid[i].clear();
        bool endflag = true;
        for (int i = 1; i <= q; i++){
            if (low[i] <= high[i]){
                endflag = false;
                mid[(low[i] + high[i]) / 2].push_back(i);
            }
        }
        if (endflag) break;

        for (int i = 0; i <= m; i++){
            for (int j : mid[i]){ // ansi = maximum no of gold replaced by silver
                LL ysum = tree2.query(1, tin[T[j]]) + tree2.query(1, tin[S[j]]) - 2 * tree2.query(1, tin[L[j]]);
                if (ysum <= Y[j]){
                    ans[j] = tree1.query(1, tin[T[j]]) + tree1.query(1, tin[S[j]]) - 2 * tree1.query(1, tin[L[j]]);
                    low[j] = i + 1;
                }
                else {
                    high[j] = i - 1;
                }
            }

            if (i == m) continue;
            int a = A[C[i + 1].second], val = C[i + 1].first;
            tree1.update(tin[a], 1);
            tree1.update(tout[a], -1);
            tree2.update(tin[a], val);
            tree2.update(tout[a], -val);
        }
    }

    tree1.init();
    for (int i = 1; i <= m; i++){
        int a = A[C[i].second], val = C[i].first;
        tree1.update(tin[a], 1);
        tree1.update(tout[a], -1);
    }

    for (int i = 1; i <= q; i++) {
        int gsum = tree1.query(1, tin[T[i]]) + tree1.query(1, tin[S[i]]) - 2 * tree1.query(1, tin[L[i]]);
        if (X[i] + ans[i] >= gsum) printf("%d\n", max(0, X[i] + ans[i] - gsum));
        else printf("-1\n");
    }

    return 0;
}

Compilation message

currencies.cpp: In function 'int main()':
currencies.cpp:133:33: warning: unused variable 'val' [-Wunused-variable]
  133 |         int a = A[C[i].second], val = C[i].first;
      |                                 ^~~
currencies.cpp:76:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   76 |     scanf("%d %d %d", &n, &m, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
currencies.cpp:78:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   78 |         scanf("%d %d", &A[i], &B[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
currencies.cpp:82:39: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   82 |     for (int i = 1; i <= m; i++) scanf("%d %d", &C[i].second, &C[i].first);
      |                                  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
currencies.cpp:83:39: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   83 |     for (int i = 1; i <= q; i++) scanf("%d %d %d %lld", &S[i], &T[i], &X[i], &Y[i]);
      |                                  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 18004 KB Output is correct
2 Correct 9 ms 18004 KB Output is correct
3 Correct 10 ms 18044 KB Output is correct
4 Correct 9 ms 17992 KB Output is correct
5 Correct 23 ms 18436 KB Output is correct
6 Correct 25 ms 18648 KB Output is correct
7 Correct 22 ms 18452 KB Output is correct
8 Correct 22 ms 18580 KB Output is correct
9 Correct 21 ms 18548 KB Output is correct
10 Correct 22 ms 18576 KB Output is correct
11 Correct 26 ms 18728 KB Output is correct
12 Correct 23 ms 18544 KB Output is correct
13 Correct 23 ms 18712 KB Output is correct
14 Correct 22 ms 18608 KB Output is correct
15 Correct 22 ms 18644 KB Output is correct
16 Correct 22 ms 18652 KB Output is correct
17 Correct 23 ms 18560 KB Output is correct
18 Correct 27 ms 18612 KB Output is correct
19 Correct 21 ms 18636 KB Output is correct
20 Correct 21 ms 18580 KB Output is correct
21 Correct 21 ms 18568 KB Output is correct
22 Correct 21 ms 18644 KB Output is correct
23 Correct 20 ms 18644 KB Output is correct
24 Correct 19 ms 18644 KB Output is correct
25 Correct 20 ms 18552 KB Output is correct
26 Correct 18 ms 18596 KB Output is correct
27 Correct 17 ms 18592 KB Output is correct
28 Correct 18 ms 18580 KB Output is correct
29 Correct 18 ms 18516 KB Output is correct
30 Correct 24 ms 18564 KB Output is correct
31 Correct 22 ms 18648 KB Output is correct
32 Correct 21 ms 18596 KB Output is correct
33 Correct 22 ms 18664 KB Output is correct
34 Correct 22 ms 18640 KB Output is correct
35 Correct 22 ms 18736 KB Output is correct

Subtask #2
28.0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 18076 KB Output is correct
2 Correct 22 ms 18584 KB Output is correct
3 Correct 21 ms 18636 KB Output is correct
4 Correct 24 ms 18584 KB Output is correct
5 Correct 807 ms 44032 KB Output is correct
6 Correct 954 ms 44620 KB Output is correct
7 Correct 960 ms 45372 KB Output is correct
8 Correct 752 ms 41948 KB Output is correct
9 Correct 710 ms 41624 KB Output is correct
10 Correct 1176 ms 50100 KB Output is correct
11 Correct 1184 ms 50208 KB Output is correct
12 Correct 1136 ms 50020 KB Output is correct
13 Correct 1098 ms 49988 KB Output is correct
14 Correct 1099 ms 50004 KB Output is correct
15 Correct 1329 ms 55228 KB Output is correct
16 Correct 1367 ms 55492 KB Output is correct
17 Correct 1648 ms 54984 KB Output is correct
18 Correct 1322 ms 50512 KB Output is correct
19 Correct 1224 ms 50460 KB Output is correct
20 Correct 1177 ms 50684 KB Output is correct
21 Correct 906 ms 50508 KB Output is correct
22 Correct 866 ms 50440 KB Output is correct
23 Correct 942 ms 50608 KB Output is correct
24 Correct 913 ms 50592 KB Output is correct
25 Correct 912 ms 50204 KB Output is correct
26 Correct 870 ms 50040 KB Output is correct
27 Correct 907 ms 50096 KB Output is correct
28 Correct 680 ms 48624 KB Output is correct
29 Correct 596 ms 47860 KB Output is correct
30 Correct 678 ms 48548 KB Output is correct
31 Correct 721 ms 48420 KB Output is correct

Subtask #3
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 18076 KB Output is correct
2 Correct 23 ms 18640 KB Output is correct
3 Correct 23 ms 18612 KB Output is correct
4 Correct 26 ms 18716 KB Output is correct
5 Correct 905 ms 48204 KB Output is correct
6 Correct 917 ms 47712 KB Output is correct
7 Correct 1083 ms 44880 KB Output is correct
8 Correct 1440 ms 55592 KB Output is correct
9 Correct 1398 ms 55612 KB Output is correct
10 Correct 1402 ms 55628 KB Output is correct
11 Correct 1111 ms 55588 KB Output is correct
12 Correct 1120 ms 55716 KB Output is correct
13 Correct 1054 ms 55576 KB Output is correct
14 Correct 773 ms 55040 KB Output is correct
15 Correct 778 ms 54688 KB Output is correct
16 Correct 919 ms 55396 KB Output is correct
17 Correct 938 ms 55240 KB Output is correct

Subtask #4
32.0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 18004 KB Output is correct
2 Correct 9 ms 18004 KB Output is correct
3 Correct 10 ms 18044 KB Output is correct
4 Correct 9 ms 17992 KB Output is correct
5 Correct 23 ms 18436 KB Output is correct
6 Correct 25 ms 18648 KB Output is correct
7 Correct 22 ms 18452 KB Output is correct
8 Correct 22 ms 18580 KB Output is correct
9 Correct 21 ms 18548 KB Output is correct
10 Correct 22 ms 18576 KB Output is correct
11 Correct 26 ms 18728 KB Output is correct
12 Correct 23 ms 18544 KB Output is correct
13 Correct 23 ms 18712 KB Output is correct
14 Correct 22 ms 18608 KB Output is correct
15 Correct 22 ms 18644 KB Output is correct
16 Correct 22 ms 18652 KB Output is correct
17 Correct 23 ms 18560 KB Output is correct
18 Correct 27 ms 18612 KB Output is correct
19 Correct 21 ms 18636 KB Output is correct
20 Correct 21 ms 18580 KB Output is correct
21 Correct 21 ms 18568 KB Output is correct
22 Correct 21 ms 18644 KB Output is correct
23 Correct 20 ms 18644 KB Output is correct
24 Correct 19 ms 18644 KB Output is correct
25 Correct 20 ms 18552 KB Output is correct
26 Correct 18 ms 18596 KB Output is correct
27 Correct 17 ms 18592 KB Output is correct
28 Correct 18 ms 18580 KB Output is correct
29 Correct 18 ms 18516 KB Output is correct
30 Correct 24 ms 18564 KB Output is correct
31 Correct 22 ms 18648 KB Output is correct
32 Correct 21 ms 18596 KB Output is correct
33 Correct 22 ms 18664 KB Output is correct
34 Correct 22 ms 18640 KB Output is correct
35 Correct 22 ms 18736 KB Output is correct
36 Correct 9 ms 18076 KB Output is correct
37 Correct 22 ms 18584 KB Output is correct
38 Correct 21 ms 18636 KB Output is correct
39 Correct 24 ms 18584 KB Output is correct
40 Correct 807 ms 44032 KB Output is correct
41 Correct 954 ms 44620 KB Output is correct
42 Correct 960 ms 45372 KB Output is correct
43 Correct 752 ms 41948 KB Output is correct
44 Correct 710 ms 41624 KB Output is correct
45 Correct 1176 ms 50100 KB Output is correct
46 Correct 1184 ms 50208 KB Output is correct
47 Correct 1136 ms 50020 KB Output is correct
48 Correct 1098 ms 49988 KB Output is correct
49 Correct 1099 ms 50004 KB Output is correct
50 Correct 1329 ms 55228 KB Output is correct
51 Correct 1367 ms 55492 KB Output is correct
52 Correct 1648 ms 54984 KB Output is correct
53 Correct 1322 ms 50512 KB Output is correct
54 Correct 1224 ms 50460 KB Output is correct
55 Correct 1177 ms 50684 KB Output is correct
56 Correct 906 ms 50508 KB Output is correct
57 Correct 866 ms 50440 KB Output is correct
58 Correct 942 ms 50608 KB Output is correct
59 Correct 913 ms 50592 KB Output is correct
60 Correct 912 ms 50204 KB Output is correct
61 Correct 870 ms 50040 KB Output is correct
62 Correct 907 ms 50096 KB Output is correct
63 Correct 680 ms 48624 KB Output is correct
64 Correct 596 ms 47860 KB Output is correct
65 Correct 678 ms 48548 KB Output is correct
66 Correct 721 ms 48420 KB Output is correct
67 Correct 10 ms 18076 KB Output is correct
68 Correct 23 ms 18640 KB Output is correct
69 Correct 23 ms 18612 KB Output is correct
70 Correct 26 ms 18716 KB Output is correct
71 Correct 905 ms 48204 KB Output is correct
72 Correct 917 ms 47712 KB Output is correct
73 Correct 1083 ms 44880 KB Output is correct
74 Correct 1440 ms 55592 KB Output is correct
75 Correct 1398 ms 55612 KB Output is correct
76 Correct 1402 ms 55628 KB Output is correct
77 Correct 1111 ms 55588 KB Output is correct
78 Correct 1120 ms 55716 KB Output is correct
79 Correct 1054 ms 55576 KB Output is correct
80 Correct 773 ms 55040 KB Output is correct
81 Correct 778 ms 54688 KB Output is correct
82 Correct 919 ms 55396 KB Output is correct
83 Correct 938 ms 55240 KB Output is correct
84 Correct 816 ms 42260 KB Output is correct
85 Correct 813 ms 39800 KB Output is correct
86 Correct 774 ms 38916 KB Output is correct
87 Correct 1214 ms 50072 KB Output is correct
88 Correct 1186 ms 50148 KB Output is correct
89 Correct 1136 ms 50068 KB Output is correct
90 Correct 1191 ms 50092 KB Output is correct
91 Correct 1179 ms 50144 KB Output is correct
92 Correct 1330 ms 54004 KB Output is correct
93 Correct 1301 ms 54884 KB Output is correct
94 Correct 1301 ms 50540 KB Output is correct
95 Correct 1304 ms 50580 KB Output is correct
96 Correct 1273 ms 50552 KB Output is correct
97 Correct 1280 ms 50552 KB Output is correct
98 Correct 1047 ms 50328 KB Output is correct
99 Correct 1153 ms 50136 KB Output is correct
100 Correct 1079 ms 50348 KB Output is correct
101 Correct 1037 ms 50452 KB Output is correct
102 Correct 878 ms 50656 KB Output is correct
103 Correct 946 ms 50744 KB Output is correct
104 Correct 935 ms 50776 KB Output is correct
105 Correct 605 ms 47928 KB Output is correct
106 Correct 607 ms 48728 KB Output is correct
107 Correct 674 ms 47916 KB Output is correct
108 Correct 716 ms 48108 KB Output is correct