QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#329206 | #2918. Tree Number Generator | ngungu46 | WA | 4ms | 13792kb | C++14 | 4.3kb | 2024-02-16 14:42:48 | 2024-04-09 19:11:14 |
Judging History
answer
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <sstream>
#include <complex>
#include <ctime>
#include <cassert>
#include <functional>
#define REP(i,s,t) for(i=(s);i<(t);i++);
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pl;
typedef pair<long long, long long> pi;
typedef vector<vector<ll> > mat;
typedef priority_queue<ll, vector<ll>, greater<ll> > minpq;
const ll inf = 1ll << 60;
const ll mod = 1e9 + 7;
const long long maxn = 300030;
const double eps = 1e-9;
long long n, m, q;
vector<long long> adj[maxn];
long long timer;
vector<long long> tin;
vector<long long> tout;
long long l;
vector<vector<long long> > up;
vector<vector<long long> > resup;
vector<vector<long long> > resdown;
vector<long long> digits;
vector<long long> pow10(300000);
long long log2(long long x){
long long j = 0;
for(j=0; (1<<j)<x; j++);
return j;
}
long long pow(long long x, long long p){
if (p == 0) return 1;
if (p%2 == 1){
return (x*pow(x, p-1))%m;
}
long long half = pow(x, (long long) (p/2));
return (half*half)%m;
}
void dfs(long long v, long long p){
tin[v] = ++timer;
up[v][0] = p;
resup[v][0] = digits[v]%m;
resdown[v][0] = digits[v]%m;
for(long long i = 1; i <= l; i++){
up[v][i] = up[up[v][i-1]][i-1];
resup[v][i] = (resup[v][i-1]*pow10[1<<(i-1)])%m;
resup[v][i] = (resup[v][i]+resup[up[v][i-1]][i-1])%m;
resdown[v][i] = (resdown[up[v][i-1]][i-1]*pow10[1<<(i-1)])%m;
resdown[v][i] = (resdown[v][i]+resdown[v][i-1])%m;
// cout << "yolo " << v << " " << p << " " << i << " " << resup[v][i] << " " << resdown[v][i] << endl;
}
for(long long u: adj[v]){
if (u!=p){
dfs(u,v);
}
}
tout[v] = ++timer;
}
bool is_ancestor(long long u, long long v){
return tin[u] <= tin[v] && tout[u] >= tout[v];
}
long long lca(long long u, long long v){
if(is_ancestor(u, v)) return u;
if(is_ancestor(v, u)) return v;
for(long long i = l; i >= 0; i--){
if(!is_ancestor(up[u][i], v)){
u = up[u][i];
}
}
return up[u][0];
}
long long query(long long u, long long v){
long long ca = lca(u, v);
long long res = 0;
for(long long i = l; i >= 0; i--){
if(!is_ancestor(up[u][i], ca)){
long long x = resup[u][i];
res = (res*pow10[1<<i])%m;
res = (res+x)%m;
u = up[u][i];
}
}
u!=ca? res = (res*10+digits[u])%m: res=res;
long long power = 0;
long long res2 = 0;
for(long long i = l; i >= 0; i--){
if(!is_ancestor(up[v][i], ca)){
long long x = resdown[v][i];
x = (x*pow10[power])%m;
res2 = (res2+x)%m;
v = up[v][i];
power += 1<<i;
}
}
// cout << "left: " << res << endl;
// cout << "right: " << res2 << endl;
long long new_x;
v!=ca? new_x = (digits[v] + digits[ca]*10)%m: new_x = digits[v]%m;
// cout << new_x << " " << v << " " << ca;
new_x = (new_x*pow10[power])%m;
res2 = (res2+new_x)%m;
v!=ca? res = (res*pow10[power+2])%m: res = (res*pow10[power+1])%m;
res = (res+res2)%m;
return res;
}
int main(){
cin >> n >> m >> q;
long long x, y;
long long i;
for(long long i = 0; i < n-1; i++){
cin >> x >> y;
adj[x-1].push_back(y-1);
adj[y-1].push_back(x-1);
}
digits.assign(n, 0);
for(long long i = 0; i < n; i++){
cin >> digits[i];
}
timer = 1;
tin.resize(n);
tout.resize(n);
l = log2(n)+1;
up.assign(n, vector<long long> (l+1,0));
for(long long i = 0; i <= n+1; i++){
pow10[i] = pow(10, i);
}
resup.assign(n, vector<long long>(l+1,-1));
resdown.assign(n, vector<long long>(l+1,-1));
dfs(0, 0);
// cout << "done build" << endl;
while(q--){
long long a, b;
cin >> a >> b;
a--, b--;
cout << query(a, b) << endl;
}
}
详细
Test #1:
score: 100
Accepted
time: 4ms
memory: 12336kb
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: 3ms
memory: 12268kb
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: 13736kb
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: 13792kb
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:
263 429 976 56 31 940 168 28 487 658 273 218 944 664 498 705 709 490 61 931 421 664 632 538 876 282 145 61 430 984 589 436 780 641 69 126 625 208 629 603 566 57 355 843 705 781 514 898 804 290 366 642 429 899 716 466 371 620 252 606 690 500 412 226 495 380 61 580 805 132 423 845 618 862 924 729 637 ...
result:
wrong answer 444th lines differ - expected: '457', found: '-167'