Submission #674011

#	Time	Username	Problem	Language	Result	Execution time	Memory
674011		AmirElarbi	Factories (JOI14_factories)	C++14	100 / 100	4471 ms	221556 KiB

factories

#include <bits/stdc++.h>
#define vi vector<int>
#define ve vector
#define ll long long
#define vf vector<float>
#define vll vector<pair<ll,ll>>
#define ii pair<int,int>
#define pll pair<ll,ll>
#define vvi vector<vi>
#define vii vector<ii>
#define gii greater<ii>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define INF 1e18
#define eps 1e-7
#define eps1 1e-2
#define optimise ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define MAX_A 2e5+5
using namespace std;
int MOD = 1e9+7;
const int nax = 5e5+5;
const int nax2 = 200+5;
typedef complex<int> Point;
using cd = complex<double>;
const double PI = acos(-1);
#include"factories.h"
vii adj[nax];
bool vis[nax];
int sb[nax], par[nax];
ve<ll> dst[nax];
int dfs(int u, int p, bool type, ll cur){
    if(type){
        dst[u].pb(cur);
    }
    sb[u] = 1;
    for(auto x : adj[u]){
        if(x.fi == p || vis[x.fi]) continue;
        sb[u] += dfs(x.fi,u, type, cur+x.se);
    }
    return sb[u];
}
int getcent(int u, int p, int ms){
    for(auto x : adj[u]){
        if(vis[x.fi] || x.fi == p) continue;
        if(sb[x.fi]*2 > ms) return getcent(x.fi,u,ms);
    }
    return u;
}
void centdec(int u, int p){
    int c = getcent(u,u,dfs(u,u,0,0));
    dfs(c,c,1,0);
    vis[c] = 1, par[c] = p;
    for(auto x : adj[c]){
        if(vis[x.fi] || x .fi == p) continue;
        centdec(x.fi, c);
    }
}   
ll ans[nax];
void Init(int n, int a[], int b[], int d[]){
    for (int i = 0; i < n; ++i)
    {
        ans[i] = INF;
    }
    for (int i = 0; i < n-1; ++i)
    {
        adj[a[i]].pb({b[i], d[i]});
        adj[b[i]].pb({a[i], d[i]});
    }
    centdec(0,-1);
    for (int i = 0; i < n; ++i)
    {
        reverse(dst[i].begin(), dst[i].end());
    }
}
long long Query(int s, int x[], int t, int y[]){
    ll aff = INF;
    for (int i = 0; i < s; ++i)
    {
        int cur = x[i], cnt = 0;
        while(cur != -1){
            ans[cur] = min(ans[cur], dst[x[i]][cnt]);
            cur = par[cur], cnt++;
        }
    }
    for (int i = 0; i < t; ++i)
    {
        int cur = y[i], cnt = 0;
        while(cur != -1){
            aff = min(aff , ans[cur] + dst[y[i]][cnt]);
            cur = par[cur], cnt++;
        }
    }
    for (int i = 0; i < s; ++i)
    {
        int cur = x[i];
        while(cur != -1){
            ans[cur] = INF;
            cur = par[cur];
        }
    }
    return aff;
}

• Subtask 1: 15 / 15
• Subtask 2: 18 / 18
• Subtask 3: 67 / 67