QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#329206#2918. Tree Number Generatorngungu46WA 4ms13792kbC++144.3kb2024-02-16 14:42:482024-04-09 19:11:14

Judging History

你现在查看的是最新测评结果

  • [2024-04-09 19:11:14]
  • 管理员手动重测该提交记录
  • 测评结果:WA
  • 用时:4ms
  • 内存:13792kb
  • [2024-02-16 14:42:48]
  • 提交

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'