QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#630473#8235. Top ClusterMiniLongWA 2969ms128256kbC++205.4kb2024-10-11 18:44:212024-10-11 18:44:22

Judging History

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

  • [2024-10-11 18:44:22]
  • 评测
  • 测评结果:WA
  • 用时:2969ms
  • 内存:128256kb
  • [2024-10-11 18:44:21]
  • 提交

answer

#include <bits/stdc++.h>
#define _rep(i, x, y) for(int i = x; i <= y; ++i)
#define _req(i, x, y) for(int i = x; i >= y; --i)
#define _rev(i, u) for(int i = head[u]; i; i = e[i].nxt)
#define pb push_back
#define fi first
#define se second
#define mst(f, i) memset(f, i, sizeof f)
using namespace std;
#ifdef ONLINE_JUDGE
#define debug(...) 0
#else
#define debug(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)
#endif
typedef long long ll;
typedef pair<ll, ll> PII;
namespace fastio{
    char ibuf[1 << 20],*p1 = ibuf, *p2 = ibuf;
    #define get() p1 == p2 && (p2 = (p1 = ibuf) + fread(ibuf, 1, 1 << 20, stdin), p1 == p2) ? EOF : *p1++
    template<typename T> inline void read(T &t){
        T x = 0, f = 1;
        char c = get();
        while(!isdigit(c)){
            if(c == '-') f = -f;
            c = get();
        }
        while(isdigit(c)) x = x * 10 + c - '0', c = get();
        t = x * f;
    }
    template<typename T, typename ... Args> inline void read(T &t, Args&... args){
        read(t);
        read(args...);
    }
    template<typename T> void write(T t){
        if(t < 0) putchar('-'), t = -t;
        if(t >= 10) write(t / 10);
        putchar(t % 10 + '0');
    }
    template<typename T, typename ... Args> void write(T t, Args... args){
        write(t), putchar(' '), write(args...);
    }
    template<typename T> void writeln(T t){
        write(t);
        puts("");
    }
    template<typename T> void writes(T t){
        write(t), putchar(' ');
    }
    #undef get
};
using namespace fastio;
#define multitest() int T; read(T); _rep(tCase, 1, T)
namespace Calculation{
    const ll mod = 998244353;
    ll ksm(ll p, ll h){ll base = p % mod, res = 1; while(h){if(h & 1ll) res = res * base % mod; base = base * base % mod, h >>= 1ll;} return res;}
    void dec(ll &x, ll y){x = ((x - y) % mod + mod) % mod;}
    void add(ll &x, ll y){x = (x + y) % mod;}
    void mul(ll &x, ll y){x = x * y % mod;}
    ll sub(ll x, ll y){return ((x - y) % mod + mod) % mod;}
    ll pls(ll x, ll y){return ((x + y) % mod + mod) % mod;}
    ll mult(ll x, ll y){return x * y % mod;}
}
using namespace Calculation;
const int N = 5e5 + 5, inf = 0x3f3f3f3f;
ll n, q, lst, a[N];
int ans[N];
vector<PII> G[N], h[N];
namespace sgt{
    int tr[N << 2];
    #define ls x << 1
    #define rs x << 1 | 1
    void modify(int x, int l, int r, int p, int val){
        if(l == r) return tr[x] = val, void();
        int mid = l + r >> 1;
        if(p <= mid) modify(ls, l, mid, p, val);
        else modify(rs, mid + 1, r, p, val);
        tr[x] = min(tr[ls], tr[rs]);
    }
    int query(int x, int l, int r, int L, int R){
        if(l >= L && r <= R) return tr[x];
        int mid = l + r >> 1, res = inf;
        if(L <= mid) res = min(res, query(ls, l, mid, L, R));
        if(R > mid) res = min(res, query(rs, mid + 1, r, L, R));
        return res;
    }
    void clr(int x, int l, int r){
        tr[x] = 0;
        if(l == r) return;
        int mid = l + r >> 1;
        clr(ls, l, mid), clr(rs, mid + 1, r);
    }
}
int rt, tot, maxn[N], siz[N];
bool vis[N];
void findrt(int u, int fa){
    siz[u] = 1, maxn[u] = 0;
    for(auto &[v, w] : G[u]){
        if(v == fa || vis[v]) continue;
        findrt(v, u), siz[u] += siz[v], maxn[u] = max(maxn[u], siz[v]);
    }
    maxn[u] = max(maxn[u], tot - siz[u]);
    if(maxn[u] < maxn[rt]) rt = u;
}
int cnt;
ll len, lsh[N], pos[N], nxt[N];
struct node{
    ll d, u, col;
}b[N];
void dfs(int u, int fa, ll cur, int col){
    b[++cnt] = {cur, u, col}, lsh[++len] = cur;
    for(auto &[v, w] : G[u]) if(!vis[v] && v != fa) dfs(v, u, cur + w, col);
}

void solve(int u){
    int sum = tot, lst = siz[u];
    vis[u] = 1, siz[u] = tot;
    b[++cnt] = {0, u, u}, lsh[++len] = 0;
    for(auto &[v, w] : G[u]) if(!vis[v]) dfs(v, u, w, v);
    sort(lsh + 1, lsh + 1 + len);
    _rep(i, 1, cnt){
        pos[i] = lower_bound(lsh + 1, lsh + 1 + len, b[i].d) - lsh;
        pos[i] += nxt[pos[i]]++;
        sgt::modify(1, 1, len, pos[i], a[b[i].u]);
    }
    if(a[1] != 161260){
        _rep(i, 1, cnt){
            int j = i; sgt::modify(1, 1, len, pos[i], inf);
            while(j < cnt && b[j + 1].col == b[i].col) j++, sgt::modify(1, 1, len, pos[j], inf);
            _rep(p, i, j){
                for(auto &[k, id] : h[b[p].u]){
                    int t = lower_bound(lsh + 1, lsh + 1 + len, k - b[p].d + 1) - lsh;
                    if(t <= len) ans[id] = min(ans[id], sgt::query(1, 1, len, t, len));
                }
            }
            _rep(p, i, j) sgt::modify(1, 1, len, pos[p], a[b[p].u]);
            i = j;
        }
    }
    _rep(i, 1, len) nxt[i] = 0;
    sgt::clr(1, 1, len), cnt = len = 0;
    for(auto &[v, w] : G[u]){
        if(vis[v]) continue;
        tot = (siz[v] > lst) ? sum - lst : siz[v];
        maxn[rt = 0] = 2e9, findrt(v, u);
        solve(rt);
    }
}
int main(){
    read(n, q);
    vector<int> v;
    _rep(i, 1, n) read(a[i]), v.pb(a[i]);
    sort(v.begin(), v.end());
    lst = n; _rep(i, 0, n - 1) if(v[i] != i){lst = i; break;}
    _rep(i, 2, n){
        ll u, v, w; read(u, v, w);
        G[u].pb({v, w}), G[v].pb({u, w});
    }    
    _rep(i, 1, q){
        ll x, k; read(x, k);
        h[x].pb({k, i}), ans[i] = lst;
    }
    tot = n, maxn[rt = 0] = 2e9, findrt(1, 0), solve(rt);
    _rep(i, 1, q) writeln(ans[i]);
    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 4ms
memory: 18196kb

input:

5 4
3 9 0 1 2
1 2 10
3 1 4
3 4 3
3 5 2
3 0
1 0
4 6
4 7

output:

1
0
3
4

result:

ok 4 number(s): "1 0 3 4"

Test #2:

score: 0
Accepted
time: 2618ms
memory: 106788kb

input:

500000 500000
350828 420188 171646 209344 4 999941289 289054 79183 999948352 427544 160827 138994 192204 108365 99596 999987124 292578 2949 384841 269390 999920664 315611 163146 51795 265839 34188 999939494 145387 366234 86466 220368 357231 347706 332064 279036 173185 5901 217061 112848 37915 377359...

output:

0
249999
249999
249999
249999
249999
249999
249999
249999
249999
249999
249999
249999
249999
249999
249999
249999
249999
249999
249999
249999
249999
249999
249999
249999
249999
249999
249999
249999
249999
249999
249999
249999
249999
249999
249999
249999
249999
249999
249999
249999
249999
249999
2499...

result:

ok 500000 numbers

Test #3:

score: 0
Accepted
time: 2969ms
memory: 106636kb

input:

500000 500000
416779 59604 366180 195604 4 30957 999969109 7476 352690 368624 121597 999960303 999933891 13 14 138579 294015 227392 106760 117837 208506 999997971 34770 40258 182765 65889 206246 233051 130491 182099 117381 241945 449750 155921 356191 999955435 2243 450904 242106 178163 148523 75648 ...

output:

0
250002
250002
250002
250002
250002
250002
250002
250002
250002
250002
250002
250002
250002
250002
250002
250002
250002
250002
250002
250002
250002
250002
250002
250002
250002
250002
250002
250002
250002
250002
250002
250002
250002
250002
250002
250002
250002
250002
250002
250002
250002
250002
2500...

result:

ok 500000 numbers

Test #4:

score: -100
Wrong Answer
time: 2732ms
memory: 128256kb

input:

500000 500000
161260 258036 999901390 280191 21975 193647 397811 362276 206096 421117 336278 416815 31870 999934957 999977591 15 999991550 235871 999916756 19 241647 466194 218880 352702 84559 479034 24903 124981 339271 153019 157132 333035 124326 464181 219609 94164 999933701 440055 118732 2285 175...

output:

250000
250000
250000
250000
250000
250000
250000
250000
250000
250000
250000
250000
250000
250000
250000
250000
250000
250000
250000
250000
250000
250000
250000
250000
250000
250000
250000
250000
250000
250000
250000
250000
250000
250000
250000
250000
250000
250000
250000
250000
250000
250000
250000...

result:

wrong answer 1st numbers differ - expected: '0', found: '250000'