oj.uz

Submission #370829

# Submission time Handle Problem Language Result Execution time Memory
370829 2021-02-24T17:40:29 Z alirezasamimi100 Factories (JOI14_factories) C++17
33 / 100
 8000 ms 131064 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].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();
    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()].emplace_back(z[i],d);
      adj[z[i]].emplace_back(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 40 ms 18560 KB Output is correct
2 Correct 1606 ms 26976 KB Output is correct
3 Correct 1607 ms 27116 KB Output is correct
4 Correct 1601 ms 27116 KB Output is correct
5 Correct 1548 ms 27500 KB Output is correct
6 Correct 1292 ms 27244 KB Output is correct
7 Correct 1604 ms 27200 KB Output is correct
8 Correct 1641 ms 27088 KB Output is correct
9 Correct 1556 ms 27372 KB Output is correct
10 Correct 1288 ms 27372 KB Output is correct
11 Correct 1604 ms 27012 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 18412 KB Output is correct
2 Correct 3628 ms 103548 KB Output is correct
3 Correct 4608 ms 106580 KB Output is correct
4 Correct 3366 ms 101232 KB Output is correct
5 Correct 4430 ms 131064 KB Output is correct
6 Correct 5140 ms 107824 KB Output is correct
7 Correct 4719 ms 43948 KB Output is correct
8 Correct 3765 ms 43748 KB Output is correct
9 Correct 4104 ms 47804 KB Output is correct
10 Correct 4638 ms 45164 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 18560 KB Output is correct
2 Correct 1606 ms 26976 KB Output is correct
3 Correct 1607 ms 27116 KB Output is correct
4 Correct 1601 ms 27116 KB Output is correct
5 Correct 1548 ms 27500 KB Output is correct
6 Correct 1292 ms 27244 KB Output is correct
7 Correct 1604 ms 27200 KB Output is correct
8 Correct 1641 ms 27088 KB Output is correct
9 Correct 1556 ms 27372 KB Output is correct
10 Correct 1288 ms 27372 KB Output is correct
11 Correct 1604 ms 27012 KB Output is correct
12 Correct 16 ms 18412 KB Output is correct
13 Correct 3628 ms 103548 KB Output is correct
14 Correct 4608 ms 106580 KB Output is correct
15 Correct 3366 ms 101232 KB Output is correct
16 Correct 4430 ms 131064 KB Output is correct
17 Correct 5140 ms 107824 KB Output is correct
18 Correct 4719 ms 43948 KB Output is correct
19 Correct 3765 ms 43748 KB Output is correct
20 Correct 4104 ms 47804 KB Output is correct
21 Correct 4638 ms 45164 KB Output is correct
22 Correct 7161 ms 105936 KB Output is correct
23 Correct 6635 ms 108148 KB Output is correct
24 Execution timed out 8004 ms 109444 KB Time limit exceeded
25 Halted 0 ms 0 KB -