Submission #1108933

#	Time	Username	Problem	Language	Result	Execution time	Memory
1108933		doducanh	공장들 (JOI14_factories)	C++14	0 / 100	23 ms	136016 KiB

factories

///breaker
#pragma GCC optimize("O2")
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second
#define ii pair<int,int>
#define mp make_pair
#define in(x) freopen(x,"r",stdin)
#define out(x) freopen(x,"w",stdout)
#define bit(x,i) ((x>>i)&1)
#define lc (id<<1)
#define rc ((id<<1)^1)
const int maxn=5e5+7;
const int inf=5e5+7;
vector<ii>adj[maxn];
int sz[maxn];
bool used[maxn];
int p[25][maxn];
ll up[25][maxn];
ll minn[maxn];
vector<int>X[100005];
vector<int>Y[100005];
int h[maxn];
vector<int>ancestors[maxn];
int n,q;
int dfs(int u,int par)
{
    sz[u]=1;
    for(auto [v,w]:adj[u]){
        if(v==par||used[v])continue;
        sz[u]+=dfs(v,u);
    }
    return sz[u];
}
void dfs1(int u,int par)
{
    for(auto [v,w]:adj[u]){
        if(v==par)continue;
        p[0][v]=u;
        up[0][v]=w;
        h[v]=h[u]+1;
        dfs1(v,u);
    }
}
void dfs2(int u,int par,int cen)
{
    ancestors[u].push_back(cen);
    for(auto [v,w]:adj[u]){
        if(v==par||used[v])continue;
        dfs2(v,u,cen);
    }
}
int getcen(int u,int par,int treesize)
{
    for(auto [v,w]:adj[u]){
        if(v==par||used[v])continue;
        if((sz[v]<<1)>treesize)return getcen(v,u,treesize);
    }
    return u;
}
void buildcen(int u,int par)
{
    int C=getcen(u,0,dfs(u,0));
    used[C]=1;
    dfs2(C,0,C);
    for(auto [v,w]:adj[u]){
        if(v==par||used[v])continue;
        buildcen(v,u);
    }
}
ll path(int u,int v)
{
    if(h[u]<h[v])swap(u,v);
    int del=h[u]-h[v];
    ll ans=0;
    for(int i=20;i>=0;i--)if(bit(del,i)){
        ans+=up[i][u];
        u=p[i][u];
    }
    if(u==v)return ans;
    for(int i=20;i>=0;i--)if(p[i][u]!=p[i][v]){
        ans+=up[i][u];
        ans+=up[i][v];
        u=p[i][u];
        v=p[i][v];
    }
    ans+=up[0][u];
    ans+=up[0][v];
    return ans;
}
void Init(int N,int A[],int B[],int D[])
{
    n=N;
    for(int i=0;i<n-1;i++){
        adj[A[i]].push_back({B[i],D[i]});
        adj[B[i]].push_back({A[i],D[i]});
    }
    dfs1(0,0);
    for(int i=1;i<=20;i++){
        for(int j=0;j<n;j++){
            p[i][j]=p[i-1][p[i-1][j]];
            up[i][j]=up[i-1][j]+up[i-1][p[i-1][j]];
        }
    }
    buildcen(0,0);
    for(int i=0;i<n;i++){
        minn[i]=inf;
    }
}
long long Query(int S, int X[], int T, int Y[])
{
    vector<int>tmp;
    int s=S,t=T;
        for(int i=0;i<s;i++){
        int x=X[i];
        tmp.push_back(x);
        for(int y:ancestors[x]){
            minn[y]=min(minn[y],path(x,y));
        }
    }
    ll ans=inf;
    for(int i=0;i<t;i++){
        int x=Y[i];
        for(int y:ancestors[x]){
            ans=min(ans,minn[y]+path(x,y));
        }
    }
    for(int x:tmp){
        for(int y:ancestors[x]){
            minn[y]=inf;
        }
    }
    return ans;
}
/* stuff you should look for
 * int overflow, array bounds
 * special cases (n=1?)
 * do smth instead of nothing and stay organized
 * WRITE STUFF DOWN
 * DON'T GET STUCK ON ONE APPROACH
 */

Compilation message (stderr)

factories.cpp: In function 'int dfs(int, int)':
factories.cpp:31:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   31 |     for(auto [v,w]:adj[u]){
      |              ^
factories.cpp: In function 'void dfs1(int, int)':
factories.cpp:39:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   39 |     for(auto [v,w]:adj[u]){
      |              ^
factories.cpp: In function 'void dfs2(int, int, int)':
factories.cpp:50:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   50 |     for(auto [v,w]:adj[u]){
      |              ^
factories.cpp: In function 'int getcen(int, int, int)':
factories.cpp:57:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   57 |     for(auto [v,w]:adj[u]){
      |              ^
factories.cpp: In function 'void buildcen(int, int)':
factories.cpp:68:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   68 |     for(auto [v,w]:adj[u]){
      |              ^

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