QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#89160#5249. BanditsBalintRWA 861ms36176kbC++4.7kb2023-03-19 09:29:272023-03-19 09:29:31

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-03-19 09:29:31]
  • 评测
  • 测评结果:WA
  • 用时:861ms
  • 内存:36176kb
  • [2023-03-19 09:29:27]
  • 提交

answer

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
//#define int long long

typedef unsigned uint;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<pii> vpii;
typedef complex<double> cmplx;
template <typename T> using minPq = priority_queue<T, vector<T>, greater<T>>;
#define boost() cin.sync_with_stdio(0); cin.tie(0)
#define ms(a, x) memset(a, x, sizeof(a))
#define pb push_back
#define fs first
#define sn second
#define ALL(v) begin(v), end(v)
#define SZ(v) ((int) (v).size())
#define lbv(v, x) (lower_bound(ALL(v), x) - (v).begin())
#define ubv(v, x) (upper_bound(ALL(v), x) - (v).begin())
template <typename T> inline void UNIQUE(vector<T> &v){sort(ALL(v)); v.resize(unique(ALL(v)) - v.begin());}
const int INF = 0x3f3f3f3f;
const ll LLINF = 0x3f3f3f3f3f3f3f3f;
const double PI = acos(-1);
#define FR(i, n) for(int i = 0; i < (n); i++)
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define FORR(i, a, b) for(int i = (a); i >= (b); i--)
#define dbg(x) {cerr << #x << ' ' << x << endl;}
#define dbgArr(arr, n) {cerr << #arr; FR(_i, n) cerr << ' ' << (arr)[_i]; cerr << endl;}

typedef tree<pii, null_type, less<pii>, rb_tree_tag, tree_order_statistics_node_update> orderTree;

struct Event {
    bool type;
    int t, v;
    int d, root;

    bool operator<(const Event &e) const {
        return t < e.t;
    }
};

ostream& operator<<(ostream &os, Event e){
    return os << "{" << e.type << ' ' << e.t << ' ' << e.v << ' ' << e.d << ' ' << e.root << "}";
}

struct Edge {
    int n2, c, i;
};

const int MN = 1e5 + 5;
int n, q;
vector<Edge> adjList[MN];
vector<Event> qs[MN], upds[MN];
bool removed[MN];
int ans[MN];

int stSz[MN];

void dfs(int n1, int par){
    stSz[n1] = 1;
    for(Edge e : adjList[n1]){
        if(e.n2 != par && !removed[e.n2]){
            dfs(e.n2, n1);
            stSz[n1] += stSz[e.n2];
        }
    }
}

int findCent(int n1, int par, int osz){
    for(Edge e : adjList[n1]){
        int n2 = e.n2;
        if(n2 != par && !removed[n2] && stSz[n2] >= osz/2) return findCent(n2, n1, osz);
    }
    return n1;
}

vector<Event> events;

void dfs1(int n1, int par, int d1, int root){
    if(d1 > INF) return;

    for(Event e : upds[n1]){
        events.pb({e.type, e.t, e.v, d1, root});
    }

    for(Edge edge : adjList[n1]){
        int n2 = edge.n2;
        int d2 = d1+edge.c;
        if(n2 == par) continue;

        for(Event e : qs[edge.i]){
            events.pb({e.type, e.t, e.v, d2, root});
        }
        if(!removed[n2]) dfs1(n2, n1, d2, root);
    }
}

void solve(int init){
    dfs(init, -1);
    int cent = findCent(init, -1, stSz[init]);

    orderTree mainTree;
    vector<orderTree> sideTrees;

    for(Edge edge : adjList[cent]){
        int n2 = edge.n2;
        int d2 = edge.c;
        int root = SZ(sideTrees);

        for(Event e : qs[edge.i]){
            events.pb({e.type, e.t, e.v, d2, root});
        }

        if(!removed[n2]) dfs1(n2, cent, d2, root);
        sideTrees.pb({});
    }

    for(Event e : upds[cent]){
        events.pb({e.type, e.t, e.v, 0, SZ(sideTrees)});
    }
    sideTrees.pb({});

    sort(ALL(events));
    //dbg(cent);
    //dbgArr(events, SZ(events));

    for(Event e : events){
        if(e.type == 0){
            if(e.d >= e.v) continue;
            mainTree.insert({e.v-e.d, SZ(mainTree)});
            sideTrees[e.root].insert({e.v-e.d, SZ(sideTrees[e.root])});
        }
        else {
            ans[e.t] += SZ(mainTree) - mainTree.order_of_key({e.d, -1});
            ans[e.t] -= SZ(sideTrees[e.root]) - sideTrees[e.root].order_of_key({e.d, -1});
            //dbg(ans[e.t]);
        }
    }

    events.clear();
    removed[cent] = true;
    for(Edge e : adjList[cent]){
        int n2 = e.n2;
        if(!removed[n2]) solve(n2);
    }
}

int main(){
    cin.sync_with_stdio(0); cin.tie(0);
    cin >> n;
    assert(n < MN);

    FR(i, n-1){
        int a, b, c;
        cin >> a >> b >> c;
        a--; b--;
        adjList[a].pb({b, c, i});
        adjList[b].pb({a, c, i});
    }

    cin >> q;
    assert(q < MN);

    FR(i, q){
        char ch; cin >> ch;
        if(ch == '+'){
            int a, v;
            cin >> a >> v;
            a--;
            upds[a].pb({0, i, v});
            ans[i] = -1;
        }
        else {
            assert(ch == '?');
            int a; cin >> a; a--;
            assert(a < n-1);
            qs[a].pb({1, i, -1});
        }
    }

    solve(0);
    FR(i, q) if(ans[i] != -1) cout << ans[i] << '\n';
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 861ms
memory: 36176kb

input:

100000
2670 75097 4080
87477 75802 1712
51835 36626 2883
19412 25923 5852
23976 19312 2520
82536 19514 2492
27160 66601 4483
99087 15088 3504
47050 58820 2964
37063 5696 9901
7717 1496 4891
79136 5448 4340
22575 81285 9289
96280 3803 9877
41980 32139 2855
44236 64938 3298
5983 99947 9666
95856 62545...

output:

0
0
0
2
2
5
2
2
3
4
4
7
8
9
11
10
14
12
12
10
11
10
10
9
10
11
11
9
15
11
14
13
14
16
11
17
15
13
15
14
14
20
15
20
22
22
20
17
23
23
24
29
24
26
30
31
36
28
37
39
35
34
45
39
46
45
43
46
42
49
44
50
43
47
52
50
49
57
51
56
61
58
68
66
69
69
61
63
67
63
72
74
78
72
73
78
77
73
85
76
86
82
85
76
82
8...

result:

ok 50000 lines

Test #2:

score: 0
Accepted
time: 503ms
memory: 31948kb

input:

100000
30038 18547 1594
65857 34063 4575
36600 72585 2328
99199 77595 1590
64257 48199 589
72301 40302 5083
69474 97536 606
60079 67381 9331
65982 39033 205
84122 65285 8508
18167 44905 3704
93490 94986 5941
27155 46374 6616
36232 62969 2212
79807 68652 7199
87352 59101 6880
94571 53224 3552
63610 8...

output:

0
1
3
3
3
3
4
6
10
10
12
14
14
16
18
19
19
19
19
22
22
23
23
23
23
24
25
26
26
26
26
26
26
28
31
31
31
31
31
34
34
36
40
41
41
42
42
42
42
42
44
44
44
47
48
48
48
48
48
48
48
48
48
49
50
50
53
54
54
55
55
56
56
56
56
56
59
62
62
62
62
62
62
62
62
62
62
63
65
67
69
69
69
73
73
73
74
76
76
76
76
76
79...

result:

ok 50000 lines

Test #3:

score: 0
Accepted
time: 233ms
memory: 18544kb

input:

100000
61878 94907 27495452
40498 66053 163324081
9987 91760 269034612
88613 6169 634714395
87422 83687 263182872
22328 64374 595886322
57437 38976 201931120
75020 26926 516189886
88639 96262 269100132
88285 44915 173237252
88407 91931 174315082
12843 50312 641940581
13297 52746 120211351
89089 4638...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 50000 lines

Test #4:

score: 0
Accepted
time: 258ms
memory: 18548kb

input:

100000
45843 69600 747867718
13793 70429 681785830
79985 74443 517803908
38369 67457 257059055
49843 59820 901603712
26439 25214 598556764
10275 5998 613157018
13517 10279 61272074
45577 49749 153772596
30727 68824 827689136
21752 9334 936611496
49173 73121 899562409
67808 9217 665070707
38351 13721...

output:

0
0
0
0
3
0
0
0
0
1
1
0
4
2
0
1
1
0
2
0
3
1
0
0
0
1
1
0
1
2
1
0
0
1
0
1
1
2
2
2
0
0
0
0
2
0
1
1
0
0
3
2
0
0
0
0
0
1
0
1
0
1
0
0
0
2
2
2
0
0
1
0
0
1
1
0
0
0
1
3
2
0
0
0
0
0
0
2
2
0
0
0
0
3
2
3
1
1
0
0
3
1
1
0
2
1
1
2
1
0
1
2
1
0
4
2
1
3
1
1
1
0
0
0
0
1
3
1
1
1
2
1
2
1
0
1
1
0
0
0
2
0
0
0
3
3
1
0
1
1
...

result:

ok 50000 lines

Test #5:

score: 0
Accepted
time: 3ms
memory: 10392kb

input:

10
1 6 50
5 7 60
10 7 57
1 7 7
8 10 71
9 8 66
1 3 79
9 4 92
8 2 41
8
? 5
? 2
+ 5 159
? 7
? 4
+ 9 184
? 7
+ 3 291

output:

0
0
1
1
1

result:

ok 5 lines

Test #6:

score: 0
Accepted
time: 535ms
memory: 22708kb

input:

100000
34346 47902 18
27392 33766 77
6756 26094 49
22936 48815 19
5650 6237 49
30025 40524 59
54595 38103 73
31226 14746 66
90535 30187 7
31954 7326 41
88688 84625 35
87060 2678 4
51031 33729 53
78866 33403 76
16783 75299 96
96244 52833 50
72746 8315 62
3610 74402 43
5479 75776 55
98976 97524 74
261...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
0
0
0
0
0
0
1
0
0
0
1
0
1
0
0
0
1
0
0
0
1
0
0
0
0
0
0
1
1
0
0
1
1
0
2
0
0
3
0
1
0
1
0
2
3
0
0
0
0
0
0
1
3
0
1
0
0
1
0
0
1
0
2
2
0
0
1
0
0
0
0
1
0
0
0
0
0
1
0
0
0
1
1
1
0
0
1
2
3
0
0
1
1
2
1
1
2
0
0
1
0
0
3
1
0
0
1
2
1
1
0
1
0
1
1
0
2
0
1
...

result:

ok 50000 lines

Test #7:

score: 0
Accepted
time: 763ms
memory: 34196kb

input:

100000
64148 54183 29
11068 35332 64
25618 18806 90
77040 76732 10
84812 90880 38
42283 75749 18
16322 30644 94
36973 59934 83
29747 75832 83
65108 11462 34
56098 73933 71
13086 78104 88
61180 33475 85
14006 4857 5
3734 96760 71
71250 14549 2
33684 24761 9
14693 12183 86
16730 80793 35
4985 57321 20...

output:

0
0
3
3
3
5
8
10
10
11
12
13
12
13
13
13
14
14
15
16
16
18
17
21
23
22
23
22
22
26
26
33
36
37
36
36
37
36
38
39
41
38
39
42
43
42
42
46
46
46
48
53
49
52
53
54
53
56
58
57
54
59
59
58
58
59
59
55
58
62
58
62
62
60
60
68
68
65
64
70
69
70
72
78
78
76
76
76
77
80
79
80
82
80
84
85
84
86
89
87
83
90
9...

result:

ok 50000 lines

Test #8:

score: 0
Accepted
time: 767ms
memory: 31084kb

input:

100000
14082 229 36
27210 94270 83
4742 68213 50
87953 67081 92
51909 51726 24
90045 60667 69
24283 69653 69
315 54923 19
44878 20782 60
65714 37239 18
18550 90268 99
90511 90267 26
74527 52573 9
44461 37153 92
94712 75548 81
54222 86266 71
99559 95348 72
19824 84320 53
57415 91290 10
1848 64264 73
...

output:

29569
22292
26968
29422
29480
29605
28379
19743
24389
24969
24814
19826
28407
22403
29124
28900
24214
21261
20969
29297
22382
27345
16938
24009
21936
21580
28754
27089
26016
28921
28981
26058
26175
17364
29296
20002
27815
29591
23866
26980
26606
20345
27293
19831
20130
18982
27761
25353
21109
16845
...

result:

ok 50000 lines

Test #9:

score: 0
Accepted
time: 3ms
memory: 10388kb

input:

10
5 9 19
10 7 2
7 8 62
4 6 79
1 4 34
2 10 44
2 3 27
6 3 52
1 9 65
8
+ 7 67
? 2
+ 2 15
? 5
? 5
? 5
+ 9 6
? 9

output:

1
0
0
0
0

result:

ok 5 lines

Test #10:

score: -100
Wrong Answer
time: 529ms
memory: 26628kb

input:

100000
76345 58764 90
38618 20579 17
64447 62815 58
59951 76798 55
74438 62576 95
53180 2222 89
11870 17020 38
39889 48984 74
16333 40563 97
25845 69446 58
5310 92817 62
3253 1870 7
89005 49525 84
82761 65333 77
84354 79477 21
580 24067 88
37079 78987 1
71193 72699 69
74616 30155 89
57080 85169 71
6...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
1
1
0
0
0
0
0
0
0
0
1
0
0
1
0
0
0
0
0
0
0
...

result:

wrong answer 39413th lines differ - expected: '16', found: '15'