oj.uz

Submission #370810

# Submission time Handle Problem Language Result Execution time Memory
370810 2021-02-24T16:56:56 Z alirezasamimi100 Factories (JOI14_factories) C++17
15 / 100
 8000 ms 104300 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],di[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);
    }
}
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(di,63,sizeof di);
    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);
      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]);
    if(!mp[z[0]]) di[z[0]]=0,pq.push(z[0]),iq[z[0]]=1;
    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]);
      if(!mp[z[i]]) di[z[i]]=0,iq[z[i]]=1,pq.push(z[i]);
    }
    while(!pq.empty()){
      auto v=pq.front();
      pq.pop();
      if(mp[v]==1) ans=min(ans,di[v]);
      iq[v]=0;
      for(auto [u,w] : adj[v]){
        if(di[v]+w<di[u]){
          di[u]=di[v]+w;
          if(!iq[u]) pq.push(u);
        }
      }
    }
    for(int i : z){
        mp[i]=-1;
        di[i]=di[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:109:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  109 |     for(int i=1; i<z.size(); i++){
      |                  ~^~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 18560 KB Output is correct
2 Correct 2621 ms 26988 KB Output is correct
3 Correct 3099 ms 27120 KB Output is correct
4 Correct 2791 ms 27280 KB Output is correct
5 Correct 2560 ms 27372 KB Output is correct
6 Correct 1971 ms 26988 KB Output is correct
7 Correct 3135 ms 26956 KB Output is correct
8 Correct 2849 ms 27244 KB Output is correct
9 Correct 2562 ms 27244 KB Output is correct
10 Correct 1976 ms 27116 KB Output is correct
11 Correct 3065 ms 26988 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 18284 KB Output is correct
2 Correct 4897 ms 102108 KB Output is correct
3 Execution timed out 8105 ms 104300 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 18560 KB Output is correct
2 Correct 2621 ms 26988 KB Output is correct
3 Correct 3099 ms 27120 KB Output is correct
4 Correct 2791 ms 27280 KB Output is correct
5 Correct 2560 ms 27372 KB Output is correct
6 Correct 1971 ms 26988 KB Output is correct
7 Correct 3135 ms 26956 KB Output is correct
8 Correct 2849 ms 27244 KB Output is correct
9 Correct 2562 ms 27244 KB Output is correct
10 Correct 1976 ms 27116 KB Output is correct
11 Correct 3065 ms 26988 KB Output is correct
12 Correct 17 ms 18284 KB Output is correct
13 Correct 4897 ms 102108 KB Output is correct
14 Execution timed out 8105 ms 104300 KB Time limit exceeded
15 Halted 0 ms 0 KB -