oj.uz

Submission #398128

# Submission time Handle Problem Language Result Execution time Memory
398128 2021-05-03T18:16:43 Z bonopo Factories (JOI14_factories) C++17
33 / 100
 8000 ms 245420 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
#define pb push_back
#define el "\n"
#define f first
#define s second

#pragma GCC optimize("O3")
#pragma GCC target("sse4")

typedef long long ll;
const ll MM=5e5+5, MOD=1e9+7, LOG=21;
int dep[MM], sz[MM], nxt[MM], in[MM], ot[MM], ct=1; ll dst[MM], spc[MM];
vector<pair<int,int>> adj[MM];
pair<int,int> st[LOG][5*MM];
bool blk[MM];

void df1(int u, int pa) {
    dep[u]=dep[pa]+1; st[0][ct]={dep[u], u}; in[u]=ct++;
    for(pair<int,int> &e:adj[u]) {
        int v=e.f, w=e.s; if(v==pa) continue;
        dst[v]=dst[u]+w; df1(v, u); sz[u]+=sz[v];
        st[0][ct++]={dep[u], u}; }
    ot[u]=ct; }
inline int qry(int l, int r) {
    int lg=log2(r-l+1);
    int x=min(st[lg][l], st[lg][r-(1<<lg)+1]).s; return x; }
inline int lca(int u, int v) {
    if(in[u]>in[v]) swap(u, v);
    return qry(in[u], in[v]); }
void gsz(int u, int pa) {
    sz[u]=1;
    for(pair<int,int> &e:adj[u]) {
        int v=e.f; if(blk[v]||v==pa) continue;
        gsz(v, u); sz[u]+=sz[v]; } }
int ctr(int u, int pa, int nd) {
    for(pair<int,int> &e:adj[u]) {
        int v=e.f; if(blk[v]||v==pa) continue;
        if(sz[v]*2>nd) return ctr(v, u, nd); }
    return u; }
inline ll dist(int u, int v) {
    return dst[u]+dst[v]-2LL*dst[lca(u, v)]; }
void slv(int u, int pa) {
    gsz(u, -1); u=ctr(u, -1, sz[u]); blk[u]=1; nxt[u]=pa;
    for(pair<int,int> &e:adj[u]) {
        int v=e.f; if(!blk[v]) slv(v, u); } }
void Init(int N, int A[], int B[], int D[]) {
    for(int i=0; i<N; ++i) spc[i]=1e18;
    for(int i=0; i<N-1; ++i) {
        adj[A[i]].emplace_back(B[i], D[i]); adj[B[i]].emplace_back(A[i], D[i]); }
    df1(0, 0); slv(0, -1);
    for(int i=1; i<LOG; ++i)
        for(int j=1; j+(1<<i)-1<=ct; ++j)
            st[i][j]=min(st[i-1][j], st[i-1][j+(1<<(i-1))]); }
long long Query(int S, int X[], int T, int Y[]) {
    for(int i=0, c; i<S; ++i) {
        c=X[i];
        while(c!=-1)
            spc[c]=min(spc[c], dist(X[i], c)), c=nxt[c], assert(c!=nxt[c]); }
    long long ans=1e18;
    for(int i=0, c; i<T; ++i) {
        c=Y[i];
        while(c!=-1)
            ans=min(ans, dist(Y[i], c)+spc[c]), c=nxt[c], assert(c!=nxt[c]); }
    for(int i=0, c; i<S; ++i) {
        c=X[i];
        while(c!=-1)
            spc[c]=1e18, c=nxt[c], assert(c!=nxt[c]); }
    return ans;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 12708 KB Output is correct
2 Correct 920 ms 22768 KB Output is correct
3 Correct 1226 ms 22788 KB Output is correct
4 Correct 1204 ms 22780 KB Output is correct
5 Correct 1210 ms 23076 KB Output is correct
6 Correct 467 ms 22776 KB Output is correct
7 Correct 1200 ms 22804 KB Output is correct
8 Correct 1306 ms 22888 KB Output is correct
9 Correct 1176 ms 23100 KB Output is correct
10 Correct 404 ms 22824 KB Output is correct
11 Correct 1200 ms 22852 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 12364 KB Output is correct
2 Correct 3413 ms 216608 KB Output is correct
3 Correct 4399 ms 212804 KB Output is correct
4 Correct 1120 ms 218328 KB Output is correct
5 Correct 6003 ms 245420 KB Output is correct
6 Correct 4693 ms 218512 KB Output is correct
7 Correct 3497 ms 70624 KB Output is correct
8 Correct 631 ms 71224 KB Output is correct
9 Correct 3993 ms 74896 KB Output is correct
10 Correct 3701 ms 71956 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 12708 KB Output is correct
2 Correct 920 ms 22768 KB Output is correct
3 Correct 1226 ms 22788 KB Output is correct
4 Correct 1204 ms 22780 KB Output is correct
5 Correct 1210 ms 23076 KB Output is correct
6 Correct 467 ms 22776 KB Output is correct
7 Correct 1200 ms 22804 KB Output is correct
8 Correct 1306 ms 22888 KB Output is correct
9 Correct 1176 ms 23100 KB Output is correct
10 Correct 404 ms 22824 KB Output is correct
11 Correct 1200 ms 22852 KB Output is correct
12 Correct 11 ms 12364 KB Output is correct
13 Correct 3413 ms 216608 KB Output is correct
14 Correct 4399 ms 212804 KB Output is correct
15 Correct 1120 ms 218328 KB Output is correct
16 Correct 6003 ms 245420 KB Output is correct
17 Correct 4693 ms 218512 KB Output is correct
18 Correct 3497 ms 70624 KB Output is correct
19 Correct 631 ms 71224 KB Output is correct
20 Correct 3993 ms 74896 KB Output is correct
21 Correct 3701 ms 71956 KB Output is correct
22 Correct 5166 ms 214356 KB Output is correct
23 Correct 5250 ms 216552 KB Output is correct
24 Correct 7222 ms 216860 KB Output is correct
25 Correct 7077 ms 220368 KB Output is correct
26 Correct 7284 ms 216984 KB Output is correct
27 Execution timed out 8053 ms 238456 KB Time limit exceeded
28 Halted 0 ms 0 KB -