Submission #482008

#	Time	Username	Problem	Language	Result	Execution time	Memory
482008		MilosMilutinovic	Factories (JOI14_factories)	C++14	100 / 100	5238 ms	414512 KiB

factories

#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 (stderr)

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 / 15
• Subtask 2: 18 / 18
• Subtask 3: 67 / 67