oj.uz

Submission #370832

# Submission time Handle Problem Language Result Execution time Memory
370832 2021-02-24T17:47:08 Z alirezasamimi100 Factories (JOI14_factories) C++17
33 / 100
 8000 ms 131028 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.clear();
    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]].clear();
    for(int i=1; i<z.size(); i++){
      adj[z[i]].clear();
      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 40 ms 18540 KB Output is correct
2 Correct 1847 ms 27200 KB Output is correct
3 Correct 1608 ms 26988 KB Output is correct
4 Correct 1587 ms 27372 KB Output is correct
5 Correct 1540 ms 27500 KB Output is correct
6 Correct 1273 ms 27176 KB Output is correct
7 Correct 1576 ms 27136 KB Output is correct
8 Correct 1557 ms 27300 KB Output is correct
9 Correct 1528 ms 27372 KB Output is correct
10 Correct 1268 ms 26988 KB Output is correct
11 Correct 1561 ms 27324 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 3612 ms 103636 KB Output is correct
3 Correct 4573 ms 106476 KB Output is correct
4 Correct 3382 ms 101236 KB Output is correct
5 Correct 4501 ms 131028 KB Output is correct
6 Correct 5187 ms 107844 KB Output is correct
7 Correct 4872 ms 43920 KB Output is correct
8 Correct 3950 ms 43756 KB Output is correct
9 Correct 4077 ms 47900 KB Output is correct
10 Correct 4578 ms 45164 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 18540 KB Output is correct
2 Correct 1847 ms 27200 KB Output is correct
3 Correct 1608 ms 26988 KB Output is correct
4 Correct 1587 ms 27372 KB Output is correct
5 Correct 1540 ms 27500 KB Output is correct
6 Correct 1273 ms 27176 KB Output is correct
7 Correct 1576 ms 27136 KB Output is correct
8 Correct 1557 ms 27300 KB Output is correct
9 Correct 1528 ms 27372 KB Output is correct
10 Correct 1268 ms 26988 KB Output is correct
11 Correct 1561 ms 27324 KB Output is correct
12 Correct 14 ms 18284 KB Output is correct
13 Correct 3612 ms 103636 KB Output is correct
14 Correct 4573 ms 106476 KB Output is correct
15 Correct 3382 ms 101236 KB Output is correct
16 Correct 4501 ms 131028 KB Output is correct
17 Correct 5187 ms 107844 KB Output is correct
18 Correct 4872 ms 43920 KB Output is correct
19 Correct 3950 ms 43756 KB Output is correct
20 Correct 4077 ms 47900 KB Output is correct
21 Correct 4578 ms 45164 KB Output is correct
22 Correct 7061 ms 106216 KB Output is correct
23 Correct 6608 ms 108216 KB Output is correct
24 Correct 7953 ms 109544 KB Output is correct
25 Execution timed out 8103 ms 111388 KB Time limit exceeded
26 Halted 0 ms 0 KB -