oj.uz

Submission #246718

# Submission time Handle Problem Language Result Execution time Memory
246718 2020-07-10T01:44:30 Z LifeHappen__ Factories (JOI14_factories) C++14
100 / 100
 4335 ms 157576 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 37 ms 12536 KB Output is correct
2 Correct 1235 ms 30584 KB Output is correct
3 Correct 1290 ms 30652 KB Output is correct
4 Correct 1307 ms 30776 KB Output is correct
5 Correct 989 ms 31096 KB Output is correct
6 Correct 1042 ms 30716 KB Output is correct
7 Correct 1274 ms 30840 KB Output is correct
8 Correct 1265 ms 30968 KB Output is correct
9 Correct 997 ms 30952 KB Output is correct
10 Correct 1052 ms 30652 KB Output is correct
11 Correct 1320 ms 30712 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 12288 KB Output is correct
2 Correct 1850 ms 130032 KB Output is correct
3 Correct 2407 ms 131264 KB Output is correct
4 Correct 1392 ms 127436 KB Output is correct
5 Correct 1777 ms 150772 KB Output is correct
6 Correct 2596 ms 133548 KB Output is correct
7 Correct 2253 ms 54476 KB Output is correct
8 Correct 1444 ms 54468 KB Output is correct
9 Correct 1301 ms 57848 KB Output is correct
10 Correct 2370 ms 55796 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 12536 KB Output is correct
2 Correct 1235 ms 30584 KB Output is correct
3 Correct 1290 ms 30652 KB Output is correct
4 Correct 1307 ms 30776 KB Output is correct
5 Correct 989 ms 31096 KB Output is correct
6 Correct 1042 ms 30716 KB Output is correct
7 Correct 1274 ms 30840 KB Output is correct
8 Correct 1265 ms 30968 KB Output is correct
9 Correct 997 ms 30952 KB Output is correct
10 Correct 1052 ms 30652 KB Output is correct
11 Correct 1320 ms 30712 KB Output is correct
12 Correct 15 ms 12288 KB Output is correct
13 Correct 1850 ms 130032 KB Output is correct
14 Correct 2407 ms 131264 KB Output is correct
15 Correct 1392 ms 127436 KB Output is correct
16 Correct 1777 ms 150772 KB Output is correct
17 Correct 2596 ms 133548 KB Output is correct
18 Correct 2253 ms 54476 KB Output is correct
19 Correct 1444 ms 54468 KB Output is correct
20 Correct 1301 ms 57848 KB Output is correct
21 Correct 2370 ms 55796 KB Output is correct
22 Correct 3422 ms 138764 KB Output is correct
23 Correct 3334 ms 140848 KB Output is correct
24 Correct 4026 ms 141436 KB Output is correct
25 Correct 4335 ms 143892 KB Output is correct
26 Correct 4129 ms 140020 KB Output is correct
27 Correct 3109 ms 157576 KB Output is correct
28 Correct 2323 ms 139580 KB Output is correct
29 Correct 4045 ms 139676 KB Output is correct
30 Correct 4145 ms 139380 KB Output is correct
31 Correct 4108 ms 139784 KB Output is correct
32 Correct 1798 ms 59604 KB Output is correct
33 Correct 1592 ms 55864 KB Output is correct
34 Correct 2075 ms 52124 KB Output is correct
35 Correct 2052 ms 52216 KB Output is correct
36 Correct 2347 ms 52728 KB Output is correct
37 Correct 2393 ms 52984 KB Output is correct