QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#641861 | #2918. Tree Number Generator | enze114514 | WA | 4ms | 6324kb | C++20 | 4.7kb | 2024-10-15 02:48:05 | 2024-10-15 02:48:05 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
#define pb push_back
const ld pi = 3.14159265358979323846;
// const int mod = 998244353;
const ll INF = 1e18;
template<typename T>
T chmax(T a, T b) {
return a > b ? a : b;
}
template<typename T>
T chmin(T a, T b) {
return a > b ? b : a;
}
const int N = (int)2e5 + 1, M = N * 2;
ll c[N], p10[N], mod;
ll qpow(ll a, ll b, ll m){
ll res = 1;
a = a % m;
while(b > 0){
if(b % 2 == 1){
res = (res * a) % m;
}
a = (a * a) % m;
b /= 2;
}
return res;
}
struct LCA{
vector<int> h, w, e, ne, dep;
vector<vector<int>> fa;
vector<vector<ll>> f;
vector<ll> p;
int n, idx;
const int depth = 18;
LCA(int _n){
n = _n;
idx = 0;
dep.resize(n, (int)1e9);
fa.resize(n);
f.resize(n);
ne.resize(n * 2, 0);
h.resize(n * 2, -1);
e.resize(n * 2, 0);
p.resize(n + 1);
for(int i = 0; i < n; i++){
fa[i] = vector<int>(depth + 1);
f[i] = vector<ll>(depth + 1);
}
}
void add(int u, int v) {
e[idx] = v, ne[idx] = h[u], h[u] = idx++;
e[idx] = u, ne[idx] = h[v], h[v] = idx++;
}
void bfs(int rt) {
dep[rt] = 1;
dep[0] = 0;
p[rt] = c[rt];
queue<int> q;
q.push(rt);
while(!q.empty()){
int u = q.front();
q.pop();
for(int i = h[u]; i != -1; i = ne[i]){
int j = e[i];
if(dep[j] > dep[u] + 1){
dep[j] = dep[u] + 1;
q.push(j);
p[j] = (p[u] * 10 % mod + c[j] + mod) % mod;
fa[j][0] = u;
for(int k = 1; k <= depth; k++){
fa[j][k] = fa[fa[j][k - 1]][k - 1];
}
for(int k = 1; k <= depth; k++){
int t = fa[j][k - 1];
f[j][k] = (f[j][k - 1] * p10[1 << (k - 1)] % mod + f[t][k - 1] + mod) % mod;
}
}
}
}
}
int lca(int u, int v){
if(dep[u] < dep[v]) swap(u, v);
for(int i = depth - 1; i >= 0; i--){
if(dep[fa[u][i]] >= dep[v]){
u = fa[u][i];
}
}
if(u == v) return u;
for(int i = depth - 1; i >= 0; i--){
if (fa[u][i] != fa[v][i]){
u = fa[u][i];
v = fa[v][i];
}
}
return fa[u][0];
}
};
ll calc1(int u, int v, const LCA& lca){
int dep = lca.dep[u] - lca.dep[v], l = dep;
ll qwq = 0, p = u;
// cout << dep << endl;
for(int i = 0; i <= lca.depth; i++){
if(dep >> i & 1){
// cout << lca.f[u][i] << " " << l - (1 << i) << " " << p10[l - (1 << i)] << endl;
qwq = (qwq + lca.f[u][i] * p10[dep - (1 << i)] % mod + mod) % mod;
u = lca.fa[u][i];
dep -= (1 << i);
}
}
qwq = (qwq * 10 % mod + lca.f[u][0]) % mod;
qwq %= mod;
return qwq;
}
ll calc2(int u, int v, const LCA &lca){
ll pu = lca.p[u], pv = lca.p[v];
ll uwu = (pv - pu + mod) % mod;
return (uwu + c[u] + mod) % mod;
}
void solve(){
int n, q;
cin >> n >> mod >> q;
LCA lca(n + 1);
for(int i = 0; i < n - 1; i++){
int u, v;
cin >> u >> v;
lca.add(u, v);
}
p10[0] = 1;
for(int i = 1; i <= n; i++){
cin >> c[i];
c[i] %= mod;
lca.f[i][0] = c[i];
p10[i] = qpow(10, i, mod);
}
lca.bfs(1);
for(int i = 0; i < q; i++){
int u, v;
cin >> u >> v;
if(mod == 1){
cout << 0 << endl;
continue;
}
if(mod == 2){
cout << c[v] % 2 << endl;
continue;
}
int anc = lca.lca(u, v);
if(anc == v){
cout << calc1(u, v, lca) << endl;
}
else if(anc == u){
cout << calc2(u, v, lca) << endl;
}
else{
ll up = calc1(u, anc, lca) - c[anc];
ll down = calc2(anc, v, lca);
ll l = lca.dep[anc] - lca.dep[u] + 1;
cout << (up + down * p10[l] % mod + mod) % mod << endl;
}
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int t = 1;
// cin >> t;
while(t--){
solve();
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 5528kb
input:
2 1 4 1 2 1 3 1 2 2 1 1 1 2 2
output:
0 0 0 0
result:
ok 4 lines
Test #2:
score: 0
Accepted
time: 1ms
memory: 5636kb
input:
3 10 5 1 2 2 3 0 0 0 1 3 3 1 2 2 2 3 2 1
output:
0 0 0 0 0
result:
ok 5 lines
Test #3:
score: 0
Accepted
time: 0ms
memory: 6324kb
input:
2000 2 2000 937 1471 1672 937 356 1672 976 356 1257 356 1503 1257 783 1503 1783 937 1284 976 1955 1503 802 1257 583 1471 526 356 701 1783 393 1955 307 1955 386 1955 1070 937 1724 802 1397 1724 1140 937 422 526 1941 1955 1638 937 1469 526 1800 526 1035 1800 1009 1140 1195 1800 142 1471 1225 1469 1524...
output:
0 1 1 1 0 0 1 0 0 1 0 1 0 0 1 1 0 0 1 1 1 1 1 0 0 0 1 0 1 1 1 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 1 0 0 0 1 1 0 1 0 0 0 0 0 1 0 1 1 0 0 0 0 1 1 1 1 1 0 0 1 1 1 0 1 1 1 0 0 1 1 1 1 0 0 0 1 0 1 0 0 1 1 1 0 1 1 0 1 0 1 0 0 1 0 1 0 0 1 1 0 1 1 1 1 0 0 0 1 0 0 0 0 1 1 0 1 1 0 1 1 0 1 1 0 0 0 1 1 0 0 1 ...
result:
ok 2000 lines
Test #4:
score: -100
Wrong Answer
time: 4ms
memory: 4296kb
input:
2000 1000 2000 1664 1028 763 1664 1541 1028 1544 1664 69 1544 1473 1541 475 1541 1551 1541 579 1473 262 475 1777 475 1916 475 391 763 807 1028 1357 1028 1682 69 345 1544 234 1541 63 391 480 807 1762 1544 306 1916 1436 1777 891 391 1852 306 523 1852 264 475 313 306 1139 391 1792 69 1604 69 398 313 10...
output:
680 320 40 980 510 350 538 246 978 310 780 950 970 684 988 590 350 580 940 960 1 550 390 30 930 330 830 510 470 120 510 470 840 220 710 126 440 690 144 510 650 260 950 220 320 640 886 510 390 690 510 250 320 570 220 906 632 910 982 846 160 840 620 974 420 550 30 920 440 308 390 390 200 950 320 250 1...
result:
wrong answer 1st lines differ - expected: '263', found: '680'