Submission #947655

#	Time	Username	Problem	Language	Result	Execution time	Memory
947655		yeediot	Factories (JOI14_factories)	C++14	0 / 100	2849 ms	291948 KiB

factories

#include<bits/stdc++.h>
#include "factories.h"
using namespace std;
#define F first
#define S second
#define all(x) x.begin(),x.end()
#define pii pair<int,int>
#define pb push_back
#define sz(x) (int)(x.size())
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
#define vi vector<int>
#define vp vector<pii>
#define vvi vector<vi>
#define ykh mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count())
#define __lg(x) 63-__builtin_clzll(x)
#define pow2(x) (1LL<<x)
void __print(int x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}
#ifdef local
void setio(){freopen("/Users/iantsai/Library/Mobile Documents/com~apple~CloudDocs/cpp/Empty.md","r",stdin);}
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
void setio(){}
#define debug(x...)
#endif
const int mxn=5e5+5;
vector<pii>adj[mxn];
int cnt[mxn];
bool vis[mxn];
vector<pair<int,long long>>p[mxn];
pair<long long,long long> mn[mxn];
void cnt_sz(int v,int pa){
    cnt[v]=1;
    for(auto [u,d]:adj[v]){
        if(vis[u] or u==pa)continue;
        cnt_sz(u,v);
        cnt[v]+=cnt[u];
    }
}
int find_cen(int v,int pa,int tar){
    for(auto [u,d]:adj[v]){
        if(vis[u] or u==pa)continue;
        if(cnt[u]*2>tar)return find_cen(u,v,tar);
    }
    return v;
}
void dfs(int v,int pa,int top,int cur){
    p[v].pb({top,cur});
    for(auto [u,d]:adj[v]){
        if(vis[u] or u==pa)continue;
        dfs(u,v,top,cur+d);
    }
}
void cen(int v){
    cnt_sz(v,v);
    v=find_cen(v,v,cnt[v]);
    vis[v]=1;
    dfs(v,v,v,0);
    for(auto [u,d]:adj[v]){
        if(vis[u])continue;
        cen(u);
    }
}
void Init(int N,int A[],int B[],int D[]){
    for(int i=0;i<N-1;i++){
        adj[A[i]].pb({B[i],D[i]});
        adj[B[i]].pb({A[i],D[i]});
    }
    cen(1);
}
long long Query(int S,int X[],int T,int Y[]){
    for(int i=0;i<S;i++){
        for(auto [u,l]:p[X[i]]){
            mn[u]={1e18,1e18};
        }
    }
    for(int i=0;i<T;i++){
        for(auto [u,l]:p[Y[i]]){
            mn[u]={1e18,1e18};
        }
    }
    long long ans=1e18;
    for(int i=0;i<S;i++){
        for(auto [u,l]:p[X[i]]){
            chmin(mn[u].F,l);
        }
    }
    for(int i=0;i<T;i++){
        for(auto [u,l]:p[Y[i]]){
            chmin(mn[u].S,l);
            chmin(ans,mn[u].F+mn[u].S);
        }
    }
    for(int i=0;i<S;i++){
        for(auto [u,l]:p[X[i]]){
            chmin(ans,mn[u].F+mn[u].S);
        }
    }
    return ans;
}
 /*
 input:
 
 */















 

Compilation message (stderr)

factories.cpp: In function 'void cnt_sz(int, int)':
factories.cpp:41:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   41 |     for(auto [u,d]:adj[v]){
      |              ^
factories.cpp: In function 'int find_cen(int, int, int)':
factories.cpp:48:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   48 |     for(auto [u,d]:adj[v]){
      |              ^
factories.cpp: In function 'void dfs(int, int, int, int)':
factories.cpp:56:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   56 |     for(auto [u,d]:adj[v]){
      |              ^
factories.cpp: In function 'void cen(int)':
factories.cpp:66:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   66 |     for(auto [u,d]:adj[v]){
      |              ^
factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:80:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   80 |         for(auto [u,l]:p[X[i]]){
      |                  ^
factories.cpp:85:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   85 |         for(auto [u,l]:p[Y[i]]){
      |                  ^
factories.cpp:91:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   91 |         for(auto [u,l]:p[X[i]]){
      |                  ^
factories.cpp:96:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   96 |         for(auto [u,l]:p[Y[i]]){
      |                  ^
factories.cpp:102:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  102 |         for(auto [u,l]:p[X[i]]){
      |                  ^

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