oj.uz

답안 #827556

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
827556 2023-08-16T14:40:35 Z Hanksburger Two Currencies (JOI23_currencies) C++17
100 / 100
 592 ms 54968 KB 
#include <bits/stdc++.h>
using namespace std;
long long par[100005][20], edge[100005], depth[100005], in[100005], out[100005], l1[100005], r1[100005], l2[100005], r2[100005], x[100005], y[100005], ans[100005], bit[200005], bit2[200005], n, m, q, sz;
vector<pair<long long, long long> > adj[100005], upd;
void dfs(long long u, long long p)
{
    par[u][0]=p;
    for (long long i=1; i<20; i++)
        par[u][i]=par[par[u][i-1]][i-1];
    for (long long i=0; i<adj[u].size(); i++)
    {
        long long v=adj[u][i].first, w=adj[u][i].second;
        if (v==p)
            continue;
        depth[v]=depth[u]+1;
        edge[v]=w;
        in[w]=(++sz);
        dfs(v, u);
        out[w]=(++sz);
    }
}
void update(long long s, long long t)
{
    for (long long i=s; i<=sz; i+=i&(-i))
    {
        bit[i]+=t;
        if (t>0)
            bit2[i]++;
        else
            bit2[i]--;
    }
}
long long query(long long s)
{
    long long res=0;
    for (long long i=s; i>=1; i-=i&(-i))
        res+=bit[i];
    return res;
}
long long query2(long long s)
{
    long long res=0;
    for (long long i=s; i>=1; i-=i&(-i))
        res+=bit2[i];
    return res;
}
void recur(long long L, long long R, vector<long long> vec)
{
    if (L==R)
    {
        for (long long ind:vec)
        {
            long long res=query2(r1[ind])-query2(l1[ind]-1);
            if (l2[ind])
                res+=query2(r2[ind])-query2(l2[ind]-1);
            ans[ind]=res;
        }
        return;
    }
    long long mid=(L+R+1)/2;
    for (long long i=L; i<mid; i++)
    {
        update(in[upd[i].second], upd[i].first);
        update(out[upd[i].second], -upd[i].first);
    }
    vector<long long> ok, notok;
    for (long long ind:vec)
    {
        long long res=query(r1[ind])-query(l1[ind]-1);
        if (l2[ind])
            res+=query(r2[ind])-query(l2[ind]-1);
        if (res<=y[ind])
            ok.push_back(ind);
        else
            notok.push_back(ind);
    }
    if (ok.size())
        recur(mid, R, ok);
    for (long long i=L; i<mid; i++)
    {
        update(in[upd[i].second], -upd[i].first);
        update(out[upd[i].second], upd[i].first);
    }
    if (notok.size())
        recur(L, mid-1, notok);
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m >> q;
    for (long long i=1; i<n; i++)
    {
        long long u, v;
        cin >> u >> v;
        adj[u].push_back({v, i});
        adj[v].push_back({u, i});
    }
    dfs(1, 1);
    for (long long i=0; i<m; i++)
    {
        long long s, t;
        cin >> s >> t;
        upd.push_back({t, s});
    }
    sort(upd.begin(), upd.end());
    for (long long i=1; i<=q; i++)
    {
        long long a, b, curA, curB;
        cin >> a >> b >> x[i] >> y[i];
        if (depth[a]<depth[b])
            swap(a, b);
        curA=a, curB=b;
        if (depth[a]>depth[b])
        {
            for (long long j=19; j>=0; j--)
                if ((depth[a]-depth[b]-1)&(1<<j))
                    curA=par[curA][j];
            if (par[curA][0]==curB)
            {
                l1[i]=in[edge[curA]];
                r1[i]=in[edge[a]];
                l2[i]=-1;
                continue;
            }
            curA=par[curA][0];
        }
        for (long long j=19; j>=0; j--)
        {
            if (par[curA][j]!=par[curB][j])
            {
                curA=par[curA][j];
                curB=par[curB][j];
            }
        }
        l1[i]=in[edge[curA]];
        r1[i]=in[edge[a]];
        l2[i]=in[edge[curB]];
        r2[i]=in[edge[b]];
    }
    vector<long long> tmp;
    for (long long i=1; i<=q; i++)
        tmp.push_back(i);
    recur(0, m, tmp);
    for (long long i=0; i<m; i++)
    {
        update(in[upd[i].second], upd[i].first);
        update(out[upd[i].second], -upd[i].first);
    }
    for (long long i=1; i<=q; i++)
    {
        long long res=query2(r1[i])-query2(l1[i]-1);
        if (l2[i])
            res+=query2(r2[i])-query2(l2[i]-1);
        cout << max(-1LL, x[i]-(res-ans[i])) << '\n';
    }
}

Compilation message

currencies.cpp: In function 'void dfs(long long int, long long int)':
currencies.cpp:10:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   10 |     for (long long i=0; i<adj[u].size(); i++)
      |                         ~^~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 1 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 6 ms 3552 KB Output is correct
6 Correct 5 ms 3712 KB Output is correct
7 Correct 5 ms 3540 KB Output is correct
8 Correct 6 ms 3668 KB Output is correct
9 Correct 6 ms 3540 KB Output is correct
10 Correct 6 ms 3668 KB Output is correct
11 Correct 6 ms 3588 KB Output is correct
12 Correct 6 ms 3668 KB Output is correct
13 Correct 6 ms 3728 KB Output is correct
14 Correct 6 ms 3720 KB Output is correct
15 Correct 6 ms 3668 KB Output is correct
16 Correct 6 ms 3588 KB Output is correct
17 Correct 6 ms 3668 KB Output is correct
18 Correct 8 ms 3604 KB Output is correct
19 Correct 6 ms 3668 KB Output is correct
20 Correct 6 ms 3668 KB Output is correct
21 Correct 6 ms 3732 KB Output is correct
22 Correct 5 ms 3668 KB Output is correct
23 Correct 5 ms 3668 KB Output is correct
24 Correct 5 ms 3696 KB Output is correct
25 Correct 5 ms 3668 KB Output is correct
26 Correct 4 ms 3708 KB Output is correct
27 Correct 4 ms 3668 KB Output is correct
28 Correct 5 ms 3592 KB Output is correct
29 Correct 5 ms 3848 KB Output is correct
30 Correct 5 ms 3668 KB Output is correct
31 Correct 6 ms 3668 KB Output is correct
32 Correct 7 ms 3668 KB Output is correct
33 Correct 6 ms 3724 KB Output is correct
34 Correct 5 ms 3668 KB Output is correct
35 Correct 6 ms 3660 KB Output is correct

Subtask #2
28.0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 6 ms 3668 KB Output is correct
3 Correct 6 ms 3668 KB Output is correct
4 Correct 6 ms 3668 KB Output is correct
5 Correct 292 ms 46980 KB Output is correct
6 Correct 339 ms 45096 KB Output is correct
7 Correct 313 ms 47628 KB Output is correct
8 Correct 269 ms 43068 KB Output is correct
9 Correct 241 ms 42428 KB Output is correct
10 Correct 392 ms 47036 KB Output is correct
11 Correct 416 ms 47552 KB Output is correct
12 Correct 386 ms 47680 KB Output is correct
13 Correct 411 ms 48196 KB Output is correct
14 Correct 417 ms 47160 KB Output is correct
15 Correct 455 ms 54276 KB Output is correct
16 Correct 479 ms 54968 KB Output is correct
17 Correct 424 ms 54072 KB Output is correct
18 Correct 449 ms 47324 KB Output is correct
19 Correct 433 ms 47068 KB Output is correct
20 Correct 445 ms 47136 KB Output is correct
21 Correct 390 ms 52164 KB Output is correct
22 Correct 336 ms 52292 KB Output is correct
23 Correct 349 ms 52236 KB Output is correct
24 Correct 333 ms 52284 KB Output is correct
25 Correct 347 ms 49668 KB Output is correct
26 Correct 348 ms 49988 KB Output is correct
27 Correct 340 ms 50104 KB Output is correct
28 Correct 243 ms 49824 KB Output is correct
29 Correct 203 ms 51212 KB Output is correct
30 Correct 301 ms 49876 KB Output is correct
31 Correct 287 ms 50248 KB Output is correct

Subtask #3
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2684 KB Output is correct
2 Correct 5 ms 3688 KB Output is correct
3 Correct 5 ms 3724 KB Output is correct
4 Correct 6 ms 3668 KB Output is correct
5 Correct 301 ms 51692 KB Output is correct
6 Correct 242 ms 51212 KB Output is correct
7 Correct 308 ms 42948 KB Output is correct
8 Correct 449 ms 53688 KB Output is correct
9 Correct 493 ms 53832 KB Output is correct
10 Correct 400 ms 53820 KB Output is correct
11 Correct 334 ms 53912 KB Output is correct
12 Correct 343 ms 53860 KB Output is correct
13 Correct 395 ms 53768 KB Output is correct
14 Correct 302 ms 53836 KB Output is correct
15 Correct 291 ms 53616 KB Output is correct
16 Correct 417 ms 53924 KB Output is correct
17 Correct 337 ms 53784 KB Output is correct

Subtask #4
32.0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 1 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 6 ms 3552 KB Output is correct
6 Correct 5 ms 3712 KB Output is correct
7 Correct 5 ms 3540 KB Output is correct
8 Correct 6 ms 3668 KB Output is correct
9 Correct 6 ms 3540 KB Output is correct
10 Correct 6 ms 3668 KB Output is correct
11 Correct 6 ms 3588 KB Output is correct
12 Correct 6 ms 3668 KB Output is correct
13 Correct 6 ms 3728 KB Output is correct
14 Correct 6 ms 3720 KB Output is correct
15 Correct 6 ms 3668 KB Output is correct
16 Correct 6 ms 3588 KB Output is correct
17 Correct 6 ms 3668 KB Output is correct
18 Correct 8 ms 3604 KB Output is correct
19 Correct 6 ms 3668 KB Output is correct
20 Correct 6 ms 3668 KB Output is correct
21 Correct 6 ms 3732 KB Output is correct
22 Correct 5 ms 3668 KB Output is correct
23 Correct 5 ms 3668 KB Output is correct
24 Correct 5 ms 3696 KB Output is correct
25 Correct 5 ms 3668 KB Output is correct
26 Correct 4 ms 3708 KB Output is correct
27 Correct 4 ms 3668 KB Output is correct
28 Correct 5 ms 3592 KB Output is correct
29 Correct 5 ms 3848 KB Output is correct
30 Correct 5 ms 3668 KB Output is correct
31 Correct 6 ms 3668 KB Output is correct
32 Correct 7 ms 3668 KB Output is correct
33 Correct 6 ms 3724 KB Output is correct
34 Correct 5 ms 3668 KB Output is correct
35 Correct 6 ms 3660 KB Output is correct
36 Correct 2 ms 2644 KB Output is correct
37 Correct 6 ms 3668 KB Output is correct
38 Correct 6 ms 3668 KB Output is correct
39 Correct 6 ms 3668 KB Output is correct
40 Correct 292 ms 46980 KB Output is correct
41 Correct 339 ms 45096 KB Output is correct
42 Correct 313 ms 47628 KB Output is correct
43 Correct 269 ms 43068 KB Output is correct
44 Correct 241 ms 42428 KB Output is correct
45 Correct 392 ms 47036 KB Output is correct
46 Correct 416 ms 47552 KB Output is correct
47 Correct 386 ms 47680 KB Output is correct
48 Correct 411 ms 48196 KB Output is correct
49 Correct 417 ms 47160 KB Output is correct
50 Correct 455 ms 54276 KB Output is correct
51 Correct 479 ms 54968 KB Output is correct
52 Correct 424 ms 54072 KB Output is correct
53 Correct 449 ms 47324 KB Output is correct
54 Correct 433 ms 47068 KB Output is correct
55 Correct 445 ms 47136 KB Output is correct
56 Correct 390 ms 52164 KB Output is correct
57 Correct 336 ms 52292 KB Output is correct
58 Correct 349 ms 52236 KB Output is correct
59 Correct 333 ms 52284 KB Output is correct
60 Correct 347 ms 49668 KB Output is correct
61 Correct 348 ms 49988 KB Output is correct
62 Correct 340 ms 50104 KB Output is correct
63 Correct 243 ms 49824 KB Output is correct
64 Correct 203 ms 51212 KB Output is correct
65 Correct 301 ms 49876 KB Output is correct
66 Correct 287 ms 50248 KB Output is correct
67 Correct 1 ms 2684 KB Output is correct
68 Correct 5 ms 3688 KB Output is correct
69 Correct 5 ms 3724 KB Output is correct
70 Correct 6 ms 3668 KB Output is correct
71 Correct 301 ms 51692 KB Output is correct
72 Correct 242 ms 51212 KB Output is correct
73 Correct 308 ms 42948 KB Output is correct
74 Correct 449 ms 53688 KB Output is correct
75 Correct 493 ms 53832 KB Output is correct
76 Correct 400 ms 53820 KB Output is correct
77 Correct 334 ms 53912 KB Output is correct
78 Correct 343 ms 53860 KB Output is correct
79 Correct 395 ms 53768 KB Output is correct
80 Correct 302 ms 53836 KB Output is correct
81 Correct 291 ms 53616 KB Output is correct
82 Correct 417 ms 53924 KB Output is correct
83 Correct 337 ms 53784 KB Output is correct
84 Correct 366 ms 43004 KB Output is correct
85 Correct 350 ms 36776 KB Output is correct
86 Correct 291 ms 35968 KB Output is correct
87 Correct 547 ms 47184 KB Output is correct
88 Correct 514 ms 47340 KB Output is correct
89 Correct 530 ms 47052 KB Output is correct
90 Correct 514 ms 46948 KB Output is correct
91 Correct 526 ms 47236 KB Output is correct
92 Correct 592 ms 52072 KB Output is correct
93 Correct 524 ms 53700 KB Output is correct
94 Correct 526 ms 47316 KB Output is correct
95 Correct 481 ms 47236 KB Output is correct
96 Correct 566 ms 47280 KB Output is correct
97 Correct 489 ms 47152 KB Output is correct
98 Correct 473 ms 52308 KB Output is correct
99 Correct 419 ms 52088 KB Output is correct
100 Correct 454 ms 52248 KB Output is correct
101 Correct 433 ms 52364 KB Output is correct
102 Correct 398 ms 48220 KB Output is correct
103 Correct 381 ms 48548 KB Output is correct
104 Correct 414 ms 48664 KB Output is correct
105 Correct 268 ms 48608 KB Output is correct
106 Correct 260 ms 49032 KB Output is correct
107 Correct 361 ms 49228 KB Output is correct
108 Correct 325 ms 48916 KB Output is correct