oj.uz

Submission #370837

# Submission time Handle Problem Language Result Execution time Memory
370837 2021-02-24T18:01:38 Z alirezasamimi100 Factories (JOI14_factories) C++17
100 / 100
 4488 ms 131044 KB 
#include <bits/stdc++.h>
#include <factories.h>
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
/*#pragma GCC optimize("O2")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,sse,sse2,fma")*/
using namespace std;
using ll = long long int;
#define F first
#define S second
#define pb push_back
#define lc v<<1
#define rc v<<1|1
#define fast_io ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
const int N=5e5+10,LN=19,M=2e2+10,SQ=250,inf=1e9;
const ll INF=1e18;
const int MOD=1000000007 /*998244353*/;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using pll=pair<ll,ll>;
using pii=pair<int,int>;
#define ordered_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update>
ll pow(ll x, ll y, ll mod){
    ll ans=1;
    while (y != 0) {
        if (y & 1) ans = ans * x % mod;
        y >>= 1;
        x = x * x % mod;
    }
    return ans;
}
int n,H[N],p[LN][N],ft[N],st[N],t,q,mp[N],po;
ll h[N],dp[N];
vector<pair<int,ll>> adj[N];
vector<int> z;
int s[N];
queue<int> pq;
bool iq[N];
void dfs(int v, int P=0){
    p[0][v]=P;
    st[v]=++t;
    for(auto [u,w] : adj[v]){
        if(u!=P) H[u]=H[v]+1,h[u]=h[v]+w,dfs(u,v);
    }
  	ft[v]=t;
}
void DFS(int v){
  if(!mp[v]) dp[v]=0;
  for(auto [u,w] : adj[v]){
      DFS(u);
      dp[v]=min(dp[u]+w,dp[v]);
  }
}
void sfd(int v){
  for(auto [u,w] : adj[v]){
      dp[u]=min(dp[u],dp[v]+w);
      sfd(u);
  }
}
bool cmp(int &a, int &b){
    return st[a]<st[b];
}
int LCA(int v, int u){
    if(H[u]<H[v]) swap(v,u);
    for(int i=H[u]-H[v]; i;i-=i&-i){
        u=p[__builtin_ctz(i)][u];
    }
    if(v==u) return v;
    for(int i=LN; i--;){
        if(p[i][u]!=p[i][v]) u=p[i][u],v=p[i][v];
    }
    return p[0][v];
}
ll dist(int v, int u){
    int z=LCA(v,u);
    return h[v]+h[u]-2*h[z];
}
void Init(int n, int A[], int B[], int D[]){
    fast_io;
    cin >> n;
    memset(dp,63,sizeof dp);
    memset(mp,-1,sizeof mp);
    for(int i=0; i<n-1; i++){
        int v=A[i],u=B[i],w=D[i];
        v++;
        u++;
        adj[v].emplace_back(u,w);
        adj[u].emplace_back(v,w);
    }
    dfs(H[1]=1);
    for(int i=1; i<LN; i++)
        for(int j=1; j<=n; j++)
            p[i][j]=p[i-1][p[i-1][j]];
}
ll Query(int S, int X[], int T, int Y[]){
    int x=S,y=T;
  	ll ans=INF;
    z={};
    po=0;
    for(int i=0; i<x; i++){
      int P=X[i];
      P++;
      z.pb(P);
      mp[P]=0;
    }
    for(int i=0; i<y; i++){
      int P=Y[i];
      P++;
      z.pb(P);
      if(mp[P]==0) ans=0;
      mp[P]=1;
    }
    sort(z.begin(),z.end(),cmp);
    for(int i=0; i<x+y-1; i++) z.pb(LCA(z[i],z[i+1]));
    z.pb(LCA(z[0],z[x+y-1]));
    sort(z.begin(),z.end(),cmp);
    z.resize(unique(z.begin(),z.end())-z.begin());
    s[++po]=z[0];
    adj[z[0]]={};
    for(int i=1; i<z.size(); i++){
      adj[z[i]]={};
      while(st[z[i]]<st[s[po]] || st[z[i]]>ft[s[po]]) po--;
      ll d=h[z[i]]-h[s[po]];
      adj[s[po]].emplace_back(z[i],d);
      s[++po]=z[i];
    }
  	DFS(z[0]);
  	sfd(z[0]);
    for(int i : z){
      	if(mp[i]==1) ans=min(ans,dp[i]);
        mp[i]=-1;
        dp[i]=dp[0];
    }
    return ans;
}

Compilation message

factories.cpp:3: warning: ignoring #pragma comment  [-Wunknown-pragmas]
    3 | #pragma comment(linker, "/stack:200000000")
      | 
factories.cpp: In function 'll Query(int, int*, int, int*)':
factories.cpp:123:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  123 |     for(int i=1; i<z.size(); i++){
      |                  ~^~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 18540 KB Output is correct
2 Correct 1231 ms 27140 KB Output is correct
3 Correct 1199 ms 27084 KB Output is correct
4 Correct 1208 ms 27372 KB Output is correct
5 Correct 1152 ms 27312 KB Output is correct
6 Correct 809 ms 26988 KB Output is correct
7 Correct 1173 ms 26988 KB Output is correct
8 Correct 1196 ms 27212 KB Output is correct
9 Correct 1108 ms 27644 KB Output is correct
10 Correct 792 ms 26988 KB Output is correct
11 Correct 1180 ms 27080 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 18284 KB Output is correct
2 Correct 2005 ms 103688 KB Output is correct
3 Correct 2502 ms 106512 KB Output is correct
4 Correct 1337 ms 101064 KB Output is correct
5 Correct 2108 ms 131044 KB Output is correct
6 Correct 2751 ms 108140 KB Output is correct
7 Correct 2614 ms 44284 KB Output is correct
8 Correct 1460 ms 43996 KB Output is correct
9 Correct 1811 ms 48236 KB Output is correct
10 Correct 2579 ms 45484 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 18540 KB Output is correct
2 Correct 1231 ms 27140 KB Output is correct
3 Correct 1199 ms 27084 KB Output is correct
4 Correct 1208 ms 27372 KB Output is correct
5 Correct 1152 ms 27312 KB Output is correct
6 Correct 809 ms 26988 KB Output is correct
7 Correct 1173 ms 26988 KB Output is correct
8 Correct 1196 ms 27212 KB Output is correct
9 Correct 1108 ms 27644 KB Output is correct
10 Correct 792 ms 26988 KB Output is correct
11 Correct 1180 ms 27080 KB Output is correct
12 Correct 14 ms 18284 KB Output is correct
13 Correct 2005 ms 103688 KB Output is correct
14 Correct 2502 ms 106512 KB Output is correct
15 Correct 1337 ms 101064 KB Output is correct
16 Correct 2108 ms 131044 KB Output is correct
17 Correct 2751 ms 108140 KB Output is correct
18 Correct 2614 ms 44284 KB Output is correct
19 Correct 1460 ms 43996 KB Output is correct
20 Correct 1811 ms 48236 KB Output is correct
21 Correct 2579 ms 45484 KB Output is correct
22 Correct 4156 ms 106216 KB Output is correct
23 Correct 3662 ms 108524 KB Output is correct
24 Correct 4488 ms 109744 KB Output is correct
25 Correct 4464 ms 113036 KB Output is correct
26 Correct 4220 ms 108688 KB Output is correct
27 Correct 3887 ms 130276 KB Output is correct
28 Correct 2334 ms 106964 KB Output is correct
29 Correct 4213 ms 108348 KB Output is correct
30 Correct 4224 ms 107908 KB Output is correct
31 Correct 4223 ms 108780 KB Output is correct
32 Correct 2357 ms 50040 KB Output is correct
33 Correct 1666 ms 46096 KB Output is correct
34 Correct 2485 ms 42092 KB Output is correct
35 Correct 2426 ms 42348 KB Output is correct
36 Correct 2578 ms 42860 KB Output is correct
37 Correct 2616 ms 42732 KB Output is correct