oj.uz

Submission #233709

# Submission time Handle Problem Language Result Execution time Memory
233709 2020-05-21T13:20:06 Z LittleFlowers__ Factories (JOI14_factories) C++17
100 / 100
 4135 ms 133196 KB 
#include <bits/stdc++.h>
using namespace std;
#define in ({int x=0;int c=getchar(),n=0;for(;!isdigit(c);c=getchar()) n=(c=='-');for(;isdigit(c);c=getchar()) x=x*10+c-'0';n?-x:x;})
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rnd(int l,int r){return l+rng()%(r-l+1);}
#define fasty ios_base::sync_with_stdio(0),cin.tie(0);
#define forinc(a,b,c) for(int a=b,_c=c;a<=_c;++a)
#define fordec(a,b,c) for(int a=b,_c=c;a>=_c;--a)
#define forv(a,b) for(auto&a:b)
#define fi first
#define se second
#define pb push_back
#define ii pair<int,long long>
#define mt make_tuple
#define all(a) a.begin(),a.end()
#define reset(f, x) memset(f, x, sizeof(f))
#define bit(x,i) ((x>>(i-1))&1)
#define on(x,i) (x|(1ll<<(i-1)))
#define off(x,i) (x&~(1<<(i-1)))
#define gg exit(0);
 
//#define unx xun
 
#ifndef unx
#include "factories.h"
const int N=500010;
#endif // unx
 
#ifdef unx
const int N=100010;
#endif // unx
const long long INF=1e15;
 
int it;
long long ret;
int st[N],ed[N],val[N];
int f[N][22];
long long pf[N],sf[N],dep[N];
vector<ii> ad[N];
 
void dfs(int u){
    st[u]=++it;
    forinc(i,1,20) f[u][i]=f[f[u][i-1]][i-1];
    forv(v,ad[u]) if(v.fi!=f[u][0]){
        f[v.fi][0]=u;
        dep[v.fi]=dep[u]+v.se;
        dfs(v.fi);
    }
    ed[u]=++it;
}
 
int anc(int u,int v){
    return st[u]<=st[v] && ed[u]>=ed[v] || !u;
}
int lca(int u,int v){
    if(anc(u,v)) return u;
    if(anc(v,u)) return v;
    fordec(i,20,0) if(!anc(f[u][i],v)) u=f[u][i];
    return f[u][0];
}
 
void Init(int n,int U[],int V[],int W[]){
    forinc(i,0,n-2){
        int u=U[i]+1, v=V[i]+1, w=W[i];
        ad[u].pb({v,w});
        ad[v].pb({u,w});
    }
    dfs(1);
    forinc(i,1,n) ad[i].clear();
}
 
void dfs1(int u){
    long long &x=pf[u], &y=sf[u];
    x=val[u]&1 ? 0 : INF, y=val[u]&2 ? 0 : INF;
    forv(v,ad[u]){
        dfs1(v.fi);
        x=min(x,pf[v.fi]+v.se), y=min(y,sf[v.fi]+v.se);
    }
    ret=min(ret,x+y);
}
 
long long Query(int s,int X[],int t,int Y[]){
    vector<int> node;
    forinc(i,0,s-1) node.push_back(X[i]+1), val[X[i]+1]=1;
    forinc(i,0,t-1) node.push_back(Y[i]+1), val[Y[i]+1]|=2;
    sort(all(node),[](int i,int j){return ii(st[i],ed[i])<ii(st[j],ed[j]);});
    forinc(i,1,node.size()-1) node.push_back(lca(node[i],node[i-1]));
    sort(all(node));
    node.erase(unique(all(node)),node.end());
    sort(all(node),[](int i,int j){return ii(st[i],ed[i])<ii(st[j],ed[j]);});
    stack<int> w;
    forv(v,node){
        while(w.size() && ed[v]>=ed[w.top()]) w.pop();
        if(w.size()){
            ad[w.top()].push_back({v,dep[v]-dep[w.top()]});
        }
        w.push(v);
    }
    ret=INF;
    dfs1(node[0]);
    forv(w,node) val[w]=pf[w]=sf[w]=0, ad[w].clear();
    //gg
    return ret;
}
 
#ifdef unx
main(){
    #define task "factory"
    freopen(task".inp","r",stdin);
    freopen(task".out","w",stdout);
 
    int n; cin>>n; int q; cin>>q;
    int x[5010], y[5010], z[5010];
    forinc(i,0,n-2) cin>>x[i]>>y[i]>>z[i];
    Init(n,x,y,z);
    while(q--){ //cerr<<q<<"\n";
        int s,t; cin>>s>>t;
        int S[5010], T[5010];
        forinc(i,0,s-1) cin>>S[i];
        forinc(i,0,t-1) cin>>T[i];
        cout<<Query(s,S,t,T)<<"\n";
    }
}
#endif

Compilation message

factories.cpp: In function 'int anc(int, int)':
factories.cpp:53:25: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
     return st[u]<=st[v] && ed[u]>=ed[v] || !u;
            ~~~~~~~~~~~~~^~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 12672 KB Output is correct
2 Correct 1257 ms 27816 KB Output is correct
3 Correct 1277 ms 27968 KB Output is correct
4 Correct 1260 ms 28024 KB Output is correct
5 Correct 985 ms 28408 KB Output is correct
6 Correct 1034 ms 28008 KB Output is correct
7 Correct 1284 ms 28152 KB Output is correct
8 Correct 1250 ms 28152 KB Output is correct
9 Correct 972 ms 28280 KB Output is correct
10 Correct 1041 ms 28084 KB Output is correct
11 Correct 1281 ms 28156 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 12416 KB Output is correct
2 Correct 1792 ms 111500 KB Output is correct
3 Correct 2435 ms 113520 KB Output is correct
4 Correct 1390 ms 109076 KB Output is correct
5 Correct 1753 ms 132360 KB Output is correct
6 Correct 2557 ms 115060 KB Output is correct
7 Correct 2268 ms 46800 KB Output is correct
8 Correct 1405 ms 46440 KB Output is correct
9 Correct 1307 ms 49668 KB Output is correct
10 Correct 2288 ms 47720 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 12672 KB Output is correct
2 Correct 1257 ms 27816 KB Output is correct
3 Correct 1277 ms 27968 KB Output is correct
4 Correct 1260 ms 28024 KB Output is correct
5 Correct 985 ms 28408 KB Output is correct
6 Correct 1034 ms 28008 KB Output is correct
7 Correct 1284 ms 28152 KB Output is correct
8 Correct 1250 ms 28152 KB Output is correct
9 Correct 972 ms 28280 KB Output is correct
10 Correct 1041 ms 28084 KB Output is correct
11 Correct 1281 ms 28156 KB Output is correct
12 Correct 14 ms 12416 KB Output is correct
13 Correct 1792 ms 111500 KB Output is correct
14 Correct 2435 ms 113520 KB Output is correct
15 Correct 1390 ms 109076 KB Output is correct
16 Correct 1753 ms 132360 KB Output is correct
17 Correct 2557 ms 115060 KB Output is correct
18 Correct 2268 ms 46800 KB Output is correct
19 Correct 1405 ms 46440 KB Output is correct
20 Correct 1307 ms 49668 KB Output is correct
21 Correct 2288 ms 47720 KB Output is correct
22 Correct 3386 ms 114808 KB Output is correct
23 Correct 3129 ms 116684 KB Output is correct
24 Correct 3812 ms 117704 KB Output is correct
25 Correct 3868 ms 119908 KB Output is correct
26 Correct 4135 ms 115768 KB Output is correct
27 Correct 3089 ms 133196 KB Output is correct
28 Correct 2303 ms 115164 KB Output is correct
29 Correct 4112 ms 115784 KB Output is correct
30 Correct 4053 ms 115380 KB Output is correct
31 Correct 4098 ms 115536 KB Output is correct
32 Correct 1826 ms 49840 KB Output is correct
33 Correct 1602 ms 45904 KB Output is correct
34 Correct 2050 ms 42616 KB Output is correct
35 Correct 2045 ms 42616 KB Output is correct
36 Correct 2309 ms 43512 KB Output is correct
37 Correct 2299 ms 43260 KB Output is correct