oj.uz

Submission #370833

# Submission time Handle Problem Language Result Execution time Memory
370833 2021-02-24T17:50:51 Z alirezasamimi100 Factories (JOI14_factories) C++17
33 / 100
 8000 ms 131188 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, int P=0){
  if(!mp[v]) dp[v]=0;
  for(auto [u,w] : adj[v]){
    if(u!=P){
      DFS(u,v);
      dp[v]=min(dp[u]+w,dp[v]);
    }
  }
}
void sfd(int v, int P=0){
  for(auto [u,w] : adj[v]){
    if(u!=P){
      dp[u]=min(dp[u],dp[v]+w);
      sfd(u,v);
    }
  }
}
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=LN; i--;){
        if(H[p[i][u]]>=H[v]) u=p[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);
      adj[z[i]].emplace_back(s[po],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:127:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  127 |     for(int i=1; i<z.size(); i++){
      |                  ~^~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 18540 KB Output is correct
2 Correct 1595 ms 27144 KB Output is correct
3 Correct 1627 ms 27116 KB Output is correct
4 Correct 1643 ms 27116 KB Output is correct
5 Correct 1550 ms 27540 KB Output is correct
6 Correct 1300 ms 27116 KB Output is correct
7 Correct 1632 ms 26988 KB Output is correct
8 Correct 1603 ms 27244 KB Output is correct
9 Correct 1512 ms 27372 KB Output is correct
10 Correct 1268 ms 27116 KB Output is correct
11 Correct 1577 ms 26988 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 3630 ms 103828 KB Output is correct
3 Correct 4681 ms 106596 KB Output is correct
4 Correct 3335 ms 101212 KB Output is correct
5 Correct 4532 ms 131188 KB Output is correct
6 Correct 5177 ms 107764 KB Output is correct
7 Correct 4644 ms 43860 KB Output is correct
8 Correct 3864 ms 44020 KB Output is correct
9 Correct 4089 ms 47828 KB Output is correct
10 Correct 4726 ms 45272 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 18540 KB Output is correct
2 Correct 1595 ms 27144 KB Output is correct
3 Correct 1627 ms 27116 KB Output is correct
4 Correct 1643 ms 27116 KB Output is correct
5 Correct 1550 ms 27540 KB Output is correct
6 Correct 1300 ms 27116 KB Output is correct
7 Correct 1632 ms 26988 KB Output is correct
8 Correct 1603 ms 27244 KB Output is correct
9 Correct 1512 ms 27372 KB Output is correct
10 Correct 1268 ms 27116 KB Output is correct
11 Correct 1577 ms 26988 KB Output is correct
12 Correct 14 ms 18284 KB Output is correct
13 Correct 3630 ms 103828 KB Output is correct
14 Correct 4681 ms 106596 KB Output is correct
15 Correct 3335 ms 101212 KB Output is correct
16 Correct 4532 ms 131188 KB Output is correct
17 Correct 5177 ms 107764 KB Output is correct
18 Correct 4644 ms 43860 KB Output is correct
19 Correct 3864 ms 44020 KB Output is correct
20 Correct 4089 ms 47828 KB Output is correct
21 Correct 4726 ms 45272 KB Output is correct
22 Correct 7127 ms 105960 KB Output is correct
23 Correct 6627 ms 108204 KB Output is correct
24 Execution timed out 8067 ms 109532 KB Time limit exceeded
25 Halted 0 ms 0 KB -