oj.uz

Submission #233691

# Submission time Handle Problem Language Result Execution time Memory
233691 2020-05-21T11:21:58 Z lfsfrlvng Factories (JOI14_factories) C++14
100 / 100
 4089 ms 139612 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 12672 KB Output is correct
2 Correct 1236 ms 22656 KB Output is correct
3 Correct 1282 ms 23544 KB Output is correct
4 Correct 1250 ms 23724 KB Output is correct
5 Correct 979 ms 23848 KB Output is correct
6 Correct 1030 ms 23804 KB Output is correct
7 Correct 1279 ms 23928 KB Output is correct
8 Correct 1245 ms 23692 KB Output is correct
9 Correct 972 ms 23932 KB Output is correct
10 Correct 1014 ms 23800 KB Output is correct
11 Correct 1266 ms 23812 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 12416 KB Output is correct
2 Correct 1799 ms 111584 KB Output is correct
3 Correct 2312 ms 113636 KB Output is correct
4 Correct 1315 ms 109032 KB Output is correct
5 Correct 1670 ms 132216 KB Output is correct
6 Correct 2461 ms 114964 KB Output is correct
7 Correct 2168 ms 41864 KB Output is correct
8 Correct 1324 ms 41600 KB Output is correct
9 Correct 1258 ms 45208 KB Output is correct
10 Correct 2278 ms 42880 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 12672 KB Output is correct
2 Correct 1236 ms 22656 KB Output is correct
3 Correct 1282 ms 23544 KB Output is correct
4 Correct 1250 ms 23724 KB Output is correct
5 Correct 979 ms 23848 KB Output is correct
6 Correct 1030 ms 23804 KB Output is correct
7 Correct 1279 ms 23928 KB Output is correct
8 Correct 1245 ms 23692 KB Output is correct
9 Correct 972 ms 23932 KB Output is correct
10 Correct 1014 ms 23800 KB Output is correct
11 Correct 1266 ms 23812 KB Output is correct
12 Correct 15 ms 12416 KB Output is correct
13 Correct 1799 ms 111584 KB Output is correct
14 Correct 2312 ms 113636 KB Output is correct
15 Correct 1315 ms 109032 KB Output is correct
16 Correct 1670 ms 132216 KB Output is correct
17 Correct 2461 ms 114964 KB Output is correct
18 Correct 2168 ms 41864 KB Output is correct
19 Correct 1324 ms 41600 KB Output is correct
20 Correct 1258 ms 45208 KB Output is correct
21 Correct 2278 ms 42880 KB Output is correct
22 Correct 3465 ms 114372 KB Output is correct
23 Correct 3258 ms 116220 KB Output is correct
24 Correct 3814 ms 117252 KB Output is correct
25 Correct 3946 ms 119736 KB Output is correct
26 Correct 4089 ms 115832 KB Output is correct
27 Correct 3078 ms 132796 KB Output is correct
28 Correct 2344 ms 114724 KB Output is correct
29 Correct 4049 ms 139536 KB Output is correct
30 Correct 4035 ms 139340 KB Output is correct
31 Correct 4006 ms 139612 KB Output is correct
32 Correct 1815 ms 59656 KB Output is correct
33 Correct 1628 ms 55948 KB Output is correct
34 Correct 2104 ms 52336 KB Output is correct
35 Correct 2052 ms 52344 KB Output is correct
36 Correct 2295 ms 53088 KB Output is correct
37 Correct 2296 ms 52856 KB Output is correct