oj.uz

Submission #370822

# Submission time Handle Problem Language Result Execution time Memory
370822 2021-02-24T17:18:58 Z alirezasamimi100 Factories (JOI14_factories) C++17
15 / 100
 8000 ms 104132 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],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);
    }
}
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(LCA(z[i],s.top())!=s.top()) s.pop();
      ll d=dist(s.top(),z[i]);
      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:126:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  126 |     for(int i=1; i<z.size(); i++){
      |                  ~^~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 18540 KB Output is correct
2 Correct 2607 ms 26988 KB Output is correct
3 Correct 3124 ms 27056 KB Output is correct
4 Correct 2873 ms 27116 KB Output is correct
5 Correct 2630 ms 27372 KB Output is correct
6 Correct 1960 ms 27116 KB Output is correct
7 Correct 3184 ms 26988 KB Output is correct
8 Correct 2863 ms 27244 KB Output is correct
9 Correct 2603 ms 27372 KB Output is correct
10 Correct 1939 ms 27040 KB Output is correct
11 Correct 3171 ms 27116 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 18284 KB Output is correct
2 Correct 4862 ms 101644 KB Output is correct
3 Execution timed out 8105 ms 104132 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 18540 KB Output is correct
2 Correct 2607 ms 26988 KB Output is correct
3 Correct 3124 ms 27056 KB Output is correct
4 Correct 2873 ms 27116 KB Output is correct
5 Correct 2630 ms 27372 KB Output is correct
6 Correct 1960 ms 27116 KB Output is correct
7 Correct 3184 ms 26988 KB Output is correct
8 Correct 2863 ms 27244 KB Output is correct
9 Correct 2603 ms 27372 KB Output is correct
10 Correct 1939 ms 27040 KB Output is correct
11 Correct 3171 ms 27116 KB Output is correct
12 Correct 16 ms 18284 KB Output is correct
13 Correct 4862 ms 101644 KB Output is correct
14 Execution timed out 8105 ms 104132 KB Time limit exceeded
15 Halted 0 ms 0 KB -