oj.uz

Submission #370827

# Submission time Handle Problem Language Result Execution time Memory
370827 2021-02-24T17:27:33 Z alirezasamimi100 Factories (JOI14_factories) C++17
33 / 100
 8000 ms 131356 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];
ll h[N],dp[N];
vector<pair<int,ll>> adj[N];
vector<int> z;
stack<int> s;
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].pb({u,w});
        adj[u].pb({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.clear();
    while(!s.empty()) s.pop();
    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.push(z[0]);
    adj[z[0]].clear();
    for(int i=1; i<z.size(); i++){
      adj[z[i]].clear();
      while(st[z[i]]<st[s.top()] || st[z[i]]>ft[s.top()]) s.pop();
      ll d=h[z[i]]-h[s.top()];
      adj[s.top()].pb({z[i],d});
      adj[z[i]].pb({s.top(),d});
      s.push(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 1559 ms 27100 KB Output is correct
3 Correct 1581 ms 27116 KB Output is correct
4 Correct 1575 ms 27116 KB Output is correct
5 Correct 1510 ms 27500 KB Output is correct
6 Correct 1266 ms 27116 KB Output is correct
7 Correct 1596 ms 27244 KB Output is correct
8 Correct 1585 ms 27204 KB Output is correct
9 Correct 1533 ms 27372 KB Output is correct
10 Correct 1260 ms 26988 KB Output is correct
11 Correct 1581 ms 27084 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 3596 ms 103668 KB Output is correct
3 Correct 4580 ms 106676 KB Output is correct
4 Correct 3297 ms 101388 KB Output is correct
5 Correct 4310 ms 131356 KB Output is correct
6 Correct 5074 ms 107904 KB Output is correct
7 Correct 4606 ms 44252 KB Output is correct
8 Correct 3755 ms 43820 KB Output is correct
9 Correct 4204 ms 48020 KB Output is correct
10 Correct 4783 ms 45472 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 1559 ms 27100 KB Output is correct
3 Correct 1581 ms 27116 KB Output is correct
4 Correct 1575 ms 27116 KB Output is correct
5 Correct 1510 ms 27500 KB Output is correct
6 Correct 1266 ms 27116 KB Output is correct
7 Correct 1596 ms 27244 KB Output is correct
8 Correct 1585 ms 27204 KB Output is correct
9 Correct 1533 ms 27372 KB Output is correct
10 Correct 1260 ms 26988 KB Output is correct
11 Correct 1581 ms 27084 KB Output is correct
12 Correct 14 ms 18284 KB Output is correct
13 Correct 3596 ms 103668 KB Output is correct
14 Correct 4580 ms 106676 KB Output is correct
15 Correct 3297 ms 101388 KB Output is correct
16 Correct 4310 ms 131356 KB Output is correct
17 Correct 5074 ms 107904 KB Output is correct
18 Correct 4606 ms 44252 KB Output is correct
19 Correct 3755 ms 43820 KB Output is correct
20 Correct 4204 ms 48020 KB Output is correct
21 Correct 4783 ms 45472 KB Output is correct
22 Correct 7100 ms 105960 KB Output is correct
23 Correct 6525 ms 108176 KB Output is correct
24 Correct 7882 ms 109600 KB Output is correct
25 Execution timed out 8039 ms 112784 KB Time limit exceeded
26 Halted 0 ms 0 KB -