QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#89160 | #5249. Bandits | BalintR | WA | 861ms | 36176kb | C++ | 4.7kb | 2023-03-19 09:29:27 | 2023-03-19 09:29:31 |
Judging History
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';
}
详细
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'