oj.uz

Submission #482008

# Submission time Handle Problem Language Result Execution time Memory
482008 2021-10-22T15:16:43 Z MilosMilutinovic Factories (JOI14_factories) C++14
100 / 100
 5238 ms 414512 KB 
#include <bits/stdc++.h>
#define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
#define fb(i,a,b) for(int (i) = (a); (i) >= (b); --(i))
#define pb push_back
#define xx first
#define yy second
#define pii pair<int,int>
#define ll long long

using namespace std;

int n;
int sajz[500005];
int par[500005][23];
vector<pii> graf[500005];
bool was[500005];
vector<pair<int, ll>> cale[500005];
int dub[500005];
ll dep[500005];

void dfs(int u, int p){
    dub[u] = dub[p] + 1;
    par[u][0] = p;
    ff(i,1,22) par[u][i] = par[par[u][i - 1]][i - 1];
    for(auto c:graf[u]){
        if(c.xx != p){
            dep[c.xx] = dep[u] + c.yy;
            dfs(c.xx, u);
        }
    }
}

int lca(int u, int v){
    if(dub[u] < dub[v])swap(u, v);
    fb(i,22,0){
        if(dub[par[u][i]] >= dub[v])u = par[u][i];
    }
    //cout << u << " " << v << "\n";
    assert(dub[u] == dub[v]);
    fb(i,22,0){
        if(par[u][i] != par[v][i]){
            u = par[u][i];
            v = par[v][i];
        }
    }
    if(u != v){
        u = par[u][0];
        v = par[v][0];
    }
    assert(u == v);
    return u;
}

ll dist(int u, int v){
    return dep[u] + dep[v] - 2 * dep[lca(u, v)];
}

void dfs1(int u, int p){
    sajz[u] = 1;
    for(auto c:graf[u]){
        if(c.xx == p || was[c.xx]) {
            continue;
        }
        dfs1(c.xx, u);
        sajz[u] += sajz[c.xx];
    }
}

int dfs2(int u, int p, int n){
    for(auto c:graf[u]){
        if(!was[c.xx] && c.xx != p && sajz[c.xx] * 2 >= n) {
            return dfs2(c.xx, u, n);
        }
    }
    return u;
}

int findcen(int u){
    dfs1(u, u);
    return dfs2(u, u, sajz[u]);
}

void solve(int u, int p, int st, ll s){
    cale[u].pb({st,s});
    for(auto c:graf[u]){
        if(c.xx != p && !was[c.xx]){
            solve(c.xx, u, st, s + c.yy);
        }
    }
}

void decomp(int u) {
    u = findcen(u);
    solve(u, u, u, 0);
    was[u] = true;
    for(auto c:graf[u]){
        if(!was[c.xx])decomp(c.xx);
    }
}

ll mn[500005];

void Init(int N, int* A, int* B, int* D){
    n = N;
    ff(i,0,n-2){
        A[i]++;
        B[i]++;
        graf[A[i]].pb({B[i], D[i]});
        graf[B[i]].pb({A[i], D[i]});
    }
    dfs(1, 0);
    decomp(1);
//    ff(i,1,n) assert((int) cale[i].size() <= 50);
    ff(i,1,n)mn[i] = 1e18;
}

ll Query(int S, int* X, int T, int* Y){
    ll ans = 1e18;
    ff(i,0,S-1)X[i]++;
    ff(i,0,T-1)Y[i]++;
    //ff(i,0,S-1) ff(j,0,T-1) ans = min(ans, dist(X[i], Y[j]));
    vector<int> cv;
    ff(i,0,S-1){
        assert(cale[i].size() <= 40);
        for(auto c:cale[X[i]]){
            mn[c.xx] = min(mn[c.xx], c.yy);
            cv.pb(c.xx);
        }
    }
    ff(i,0,T-1){
        for(auto c:cale[Y[i]]){
            ans = min(ans, mn[c.xx] + c.yy);
        }
    }
    for(auto c:cv)mn[c] = 1e18;
    return ans;
}

Compilation message

factories.cpp: In function 'void dfs(int, int)':
factories.cpp:2:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    2 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
factories.cpp:24:5: note: in expansion of macro 'ff'
   24 |     ff(i,1,22) par[u][i] = par[par[u][i - 1]][i - 1];
      |     ^~
factories.cpp: In function 'int lca(int, int)':
factories.cpp:3:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    3 | #define fb(i,a,b) for(int (i) = (a); (i) >= (b); --(i))
      |                           ^
factories.cpp:35:5: note: in expansion of macro 'fb'
   35 |     fb(i,22,0){
      |     ^~
factories.cpp:3:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    3 | #define fb(i,a,b) for(int (i) = (a); (i) >= (b); --(i))
      |                           ^
factories.cpp:40:5: note: in expansion of macro 'fb'
   40 |     fb(i,22,0){
      |     ^~
factories.cpp: In function 'void Init(int, int*, int*, int*)':
factories.cpp:2:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    2 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
factories.cpp:105:5: note: in expansion of macro 'ff'
  105 |     ff(i,0,n-2){
      |     ^~
factories.cpp:2:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    2 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
factories.cpp:114:5: note: in expansion of macro 'ff'
  114 |     ff(i,1,n)mn[i] = 1e18;
      |     ^~
factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:2:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    2 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
factories.cpp:119:5: note: in expansion of macro 'ff'
  119 |     ff(i,0,S-1)X[i]++;
      |     ^~
factories.cpp:2:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    2 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
factories.cpp:120:5: note: in expansion of macro 'ff'
  120 |     ff(i,0,T-1)Y[i]++;
      |     ^~
factories.cpp:2:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    2 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
factories.cpp:123:5: note: in expansion of macro 'ff'
  123 |     ff(i,0,S-1){
      |     ^~
factories.cpp:2:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    2 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
factories.cpp:130:5: note: in expansion of macro 'ff'
  130 |     ff(i,0,T-1){
      |     ^~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 24140 KB Output is correct
2 Correct 272 ms 33488 KB Output is correct
3 Correct 289 ms 33952 KB Output is correct
4 Correct 336 ms 34336 KB Output is correct
5 Correct 310 ms 34424 KB Output is correct
6 Correct 214 ms 32876 KB Output is correct
7 Correct 306 ms 33792 KB Output is correct
8 Correct 291 ms 33984 KB Output is correct
9 Correct 310 ms 34432 KB Output is correct
10 Correct 206 ms 32836 KB Output is correct
11 Correct 287 ms 33732 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 24076 KB Output is correct
2 Correct 2585 ms 239636 KB Output is correct
3 Correct 4066 ms 309952 KB Output is correct
4 Correct 1039 ms 136744 KB Output is correct
5 Correct 4882 ms 388160 KB Output is correct
6 Correct 3776 ms 310272 KB Output is correct
7 Correct 1052 ms 77672 KB Output is correct
8 Correct 432 ms 69272 KB Output is correct
9 Correct 1284 ms 105052 KB Output is correct
10 Correct 1113 ms 92888 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 24140 KB Output is correct
2 Correct 272 ms 33488 KB Output is correct
3 Correct 289 ms 33952 KB Output is correct
4 Correct 336 ms 34336 KB Output is correct
5 Correct 310 ms 34424 KB Output is correct
6 Correct 214 ms 32876 KB Output is correct
7 Correct 306 ms 33792 KB Output is correct
8 Correct 291 ms 33984 KB Output is correct
9 Correct 310 ms 34432 KB Output is correct
10 Correct 206 ms 32836 KB Output is correct
11 Correct 287 ms 33732 KB Output is correct
12 Correct 13 ms 24076 KB Output is correct
13 Correct 2585 ms 239636 KB Output is correct
14 Correct 4066 ms 309952 KB Output is correct
15 Correct 1039 ms 136744 KB Output is correct
16 Correct 4882 ms 388160 KB Output is correct
17 Correct 3776 ms 310272 KB Output is correct
18 Correct 1052 ms 77672 KB Output is correct
19 Correct 432 ms 69272 KB Output is correct
20 Correct 1284 ms 105052 KB Output is correct
21 Correct 1113 ms 92888 KB Output is correct
22 Correct 3024 ms 267068 KB Output is correct
23 Correct 3019 ms 274228 KB Output is correct
24 Correct 4420 ms 342316 KB Output is correct
25 Correct 4278 ms 344540 KB Output is correct
26 Correct 4102 ms 336212 KB Output is correct
27 Correct 5238 ms 414512 KB Output is correct
28 Correct 1248 ms 166248 KB Output is correct
29 Correct 3890 ms 335172 KB Output is correct
30 Correct 3870 ms 335192 KB Output is correct
31 Correct 3938 ms 335428 KB Output is correct
32 Correct 1174 ms 110264 KB Output is correct
33 Correct 442 ms 70072 KB Output is correct
34 Correct 760 ms 84144 KB Output is correct
35 Correct 784 ms 84948 KB Output is correct
36 Correct 968 ms 89924 KB Output is correct
37 Correct 995 ms 90048 KB Output is correct