QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#222906 | #7608. Cliques | ucup-team191# | WA | 3ms | 20360kb | C++14 | 3.5kb | 2023-10-21 19:37:05 | 2023-10-21 19:37:06 |
Judging History
answer
#include <cstdio>
#include <vector>
#include <algorithm>
#define X first
#define Y second
#define PB push_back
using namespace std;
typedef long long ll;
const int N = 2e5 + 500;
const int LOG = 18;
const int MOD = 1e9 + 7;
const int OFF = 1 << 18;
inline int add(int A, int B) {
if(A + B >= MOD) return A + B - MOD;
return A + B;
}
inline int sub(int A, int B) {
if(A - B < 0) return A - B + MOD;
return A - B;
}
inline int mul(int A, int B) {
return (ll)A * B % MOD;
}
inline int pot(int A, int B) {
int ret = 1, bs = A;
for(; B ; B >>= 1) {
if(B & 1) ret = mul(ret, bs);
bs = mul(bs, bs);
}
return ret;
}
int ind[N], siz[N], par[N][LOG], hat[N], dep[N], pot2[N], kof[2 * OFF];
vector < int > v[N];
int tme;
int prop[2 * OFF], T[2 * OFF], imp[N], n;
void refresh(int x) {
if(prop[x] == 1) return;
T[x] = mul(T[x], prop[x]);
if(x < OFF) {
prop[2 * x] = mul(prop[2 * x], prop[x]);
prop[2 * x + 1] = mul(prop[2 * x + 1], prop[x]);
}
prop[x] = 1;
}
void range_update(int i, int a, int b, int lo, int hi, int x) {
if(lo <= a && b <= hi) {
prop[i] = mul(prop[i], x); refresh(i); return;
}
if(a > hi || b < lo) return;
range_update(2 * i, a, (a + b) / 2, lo, hi, x);
range_update(2 * i + 1, (a + b) / 2 + 1, b, lo, hi, x);
if(2 * i < OFF) T[i] = add(T[2 * i], T[2 * i + 1]);
else T[i] = add(mul(T[2 * i], kof[2 * i]), mul(T[2 * i + 1], kof[2 * i + 1]));
}
void precompute(){
pot2[0] = 1;
for(int i = 1;i < N;i++)
pot2[i] = add(pot2[i - 1], pot2[i - 1]);
}
bool cmp(int x, int y) {
return siz[x] > siz[y];
}
void dfs_siz(int x, int lst){
siz[x] = 1; par[x][0] = lst;
dep[x] = dep[lst] + 1;
for(int y : v[x]) {
if(y == lst) continue;
dfs_siz(y, x);
siz[x] += siz[y];
}
}
void dfs(int x, int lst, int cur) {
ind[x] = tme++; hat[x] = cur;
int fir = 1;
sort(v[x].begin(), v[x].end(), cmp);
for(int y : v[x]) {
if(y == lst) continue;
dfs(y, x, fir ? cur : y);
fir = 0;
}
}
int digni(int x, int k) {
for(int i = 0;i < LOG;i++)
if(k & (1 << i)) x = par[x][i];
return x;
}
int lca(int a, int b) {
if(dep[a] < dep[b]) swap(a, b);
a = digni(a, dep[a] - dep[b]);
if(a == b) return a;
for(int k = LOG - 1;k >= 0;k--)
if(par[a][k] != par[b][k])
a = par[a][k], b = par[b][k];
return par[a][0];
}
void hld_path(int a, int b, int x) {
while(dep[hat[a]] > dep[b]) {
range_update(1, 0, OFF - 1, ind[hat[a]], ind[a], x);
a = par[hat[a]][0];
}
range_update(1, 0, OFF - 1, ind[b], ind[a], x);
}
void add_path(int a, int b, int fl) {
if(dep[a] < dep[b]) swap(a, b);
int lc = lca(a, b);
imp[lc] += fl ? 1 : -1;
kof[OFF + ind[lc]] = pot2[imp[lc]] - 1;
range_update(1, 0, OFF - 1, ind[lc], ind[lc], 1);
int fact = fl ? 2 : ((MOD + 1) / 2);
if(a != b) {
hld_path(a, digni(a, dep[a] - dep[lc] - 1), fact);
if(b != lc) hld_path(b, digni(b, dep[b] - dep[lc] - 1), fact);
}
}
int main() {
precompute();
scanf("%d", &n);
for(int i = 1;i < n;i++) {
int x, y; scanf("%d%d", &x, &y);
v[x].PB(y), v[y].PB(x);
}
dfs_siz(1, 1); dfs(1, 1, 1);
for(int j = 1;j < LOG;j++)
for(int i = 1;i <= n;i++)
par[i][j] = par[par[i][j - 1]][j - 1];
for(int i = 0;i < n;i++) T[OFF + i] = 1, prop[OFF + i] = 1;
for(int i = OFF - 1; i ; i--) {
prop[i] = 1;
}
int q; scanf("%d", &q);
for(;q--;) {
char ty; int a, b; scanf(" %c%d%d", &ty, &a, &b);
add_path(a, b, ty == '+');
printf("%d\n", T[1]);
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 3ms
memory: 20360kb
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: -100
Wrong Answer
time: 0ms
memory: 20204kb
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 256 255 259 515 1027 1283 643 385 769 1537 769 773 833 449 833 369
result:
wrong answer 15th lines differ - expected: '257', found: '256'