QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#369206 | #7608. Cliques | Delay_for_five_minutes# | WA | 165ms | 44908kb | C++20 | 3.2kb | 2024-03-27 21:56:30 | 2024-03-27 21:56:31 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
vector<int> E[200005];
const int mod = 1e9 + 7;
const int N = 200005;
int n , q;
struct hld {
int tag[N * 4];
int sum[N * 4];
void build(int u,int l,int r) {
tag[u] = 1 ; sum[u] = (r - l + 1);
if(l == r) return ;
build(u<<1 , l , (l + r >> 1));
build(u<<1|1 , (l + r >> 1) + 1 , r) ;
return ;
}
void apply(int u,int v) {
tag[u] = 1LL * tag[u] * v % mod;
sum[u] = 1LL * sum[u] * v % mod;
}
void pd(int u) {
if(tag[u] != 1) {
apply(u<<1 , tag[u]);
apply(u<<1|1 , tag[u]);
tag[u] = 1;
}
}
void modify(int u,int l,int r,int ql,int qr,int v) {
if(ql <= l && qr >= r) {
apply(u , v);
return ;
}
int md = (l + r>>1);
pd(u) ;
if(ql <= md) modify(u<<1 , l , md , ql , qr , v);
if(qr > md) modify(u<<1|1 , md + 1 , r , ql , qr , v);
sum[u] = (sum[u << 1] + sum[u << 1|1]) % mod;
return ;
}
int fa[N] , sz[N] , sn[N] , tp[N] , dfn[N] , nfd[N] , dep[N] , id;
hld() {id = 0;}
void dfs1(int u,int f) {
sz[u] = 1; fa[u] = f;
for(auto v : E[u]) {
if(v != f) {
dep[v] = dep[u] + 1;
dfs1(v , u) ; sz[u] += sz[v] ;
if(sz[sn[u]] < sz[v]) sn[u] = v;
}
}
}
void dfs2(int u,int p) {
dfn[u] = ++id ; nfd[id] = u ; tp[u] = p;
if(sn[u]) dfs2(sn[u] , p) ;
for(auto v : E[u]) {
if(v != fa[u] && v != sn[u]) dfs2(v , v);
}
}
int lca(int x,int y) {
while(tp[x] ^ tp[y]) {
if(dep[tp[x]] < dep[tp[y]]) swap(x , y);
x = fa[tp[x]] ;
}
if(dep[x] > dep[y]) swap(x , y) ;
return x;
}
void mdf(int x,int y,int v) {
while(tp[x] ^ tp[y]) {
if(dep[tp[x]] < dep[tp[y]]) swap(x , y);
modify(1 , 1 , n , dfn[x] , dfn[y] , v);
x = fa[tp[x]] ;
}
if(dep[x] > dep[y]) swap(x , y);
modify(1 , 1 , n , dfn[x] , dfn[y] , v) ;
}
}A , B;
int main() {
ios::sync_with_stdio(false) ; cin.tie(0) ; cout.tie(0) ;
cin >> n;
for(int i = 1;i < n;i++) {
int u , v;cin >> u >> v;
E[u].push_back(v) ; E[v].push_back(u) ;
}
A.dfs1(1 , 0) ; A.dfs2(1 , 1); A.build(1 , 1 , n);
B.dfs1(1 , 0) ; B.dfs2(1 , 1); B.build(1 , 1 ,n);
cin >> q;
int r2 = (mod + 1) / 2;
while(q--) {
char ch ; int u , v;
cin >> ch >> u >> v;
if(ch == '+') {
A.mdf(u , v , 2);
B.mdf(u , v , 2);
int l = B.lca(u , v);
B.mdf(l , l , r2) ;
}
else {
A.mdf(u , v , r2);
B.mdf(u , v, r2);
int l = B.lca(u , v);
B.mdf(l , l , 2) ;
}
int ans = (A.sum[1] - B.sum[1] + mod ) % mod;
cout << ans << '\n';
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 22124kb
input:
5 1 2 5 1 2 3 4 2 6 + 4 5 + 2 2 + 1 3 - 2 2 + 2 3 + 4 4
output:
1 3 7 3 7 9
result:
ok 6 lines
Test #2:
score: 0
Accepted
time: 0ms
memory: 22040kb
input:
20 8 7 19 10 12 14 3 16 17 13 7 10 5 6 1 9 15 12 5 2 16 13 3 11 20 14 18 6 1 14 16 20 11 10 3 4 20 6 30 + 10 20 + 14 20 + 12 17 - 14 20 - 12 17 + 4 6 + 8 20 + 3 6 - 10 20 + 2 17 + 1 16 + 6 10 + 9 10 + 5 15 + 7 8 - 7 8 + 2 5 + 3 18 + 1 20 + 8 16 - 3 18 - 5 15 + 4 20 + 14 16 - 4 6 + 8 19 + 4 7 - 1 16 ...
output:
1 3 7 3 1 3 7 15 7 15 31 63 127 255 257 255 259 515 1027 1283 643 385 769 1537 769 785 865 481 737 369
result:
ok 30 lines
Test #3:
score: -100
Wrong Answer
time: 165ms
memory: 44908kb
input:
131072 3641 72511 10338 18718 8949 15478 79108 62887 42154 28540 65359 102645 93744 48493 3277 103211 43542 61315 93315 118634 24021 57937 31034 436 30411 6208 1388 25159 93424 128520 119820 87281 5860 97559 59648 8225 57244 58766 119685 13716 130165 60958 79806 116338 97486 80167 101963 95499 51263...
output:
1 2 3 5 10 20 36 52 104 200 328 360 720 912 1680 1682 2210 3746 3748 7364 6276 12484 12356 14468 22660 43140 47364 90372 84100 166020 168068 299140 598148 663684 1327236 2654340 2658436 2658440 5316872 5841160 11674120 11674122 22168074 22692362 21840138 43680010 43680012 43745548 43745549 43745553 ...
result:
wrong answer 3rd lines differ - expected: '4', found: '3'