oj.uz

Submission #370831

# Submission time Handle Problem Language Result Execution time Memory
370831 2021-02-24T17:45:46 Z alirezasamimi100 Factories (JOI14_factories) C++17
33 / 100
 8000 ms 130968 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 39 ms 18540 KB Output is correct
2 Correct 1581 ms 26988 KB Output is correct
3 Correct 1651 ms 27024 KB Output is correct
4 Correct 1590 ms 27284 KB Output is correct
5 Correct 1527 ms 27372 KB Output is correct
6 Correct 1278 ms 27104 KB Output is correct
7 Correct 1599 ms 26988 KB Output is correct
8 Correct 1628 ms 27136 KB Output is correct
9 Correct 1527 ms 27372 KB Output is correct
10 Correct 1284 ms 27120 KB Output is correct
11 Correct 1592 ms 27104 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 3628 ms 103728 KB Output is correct
3 Correct 4655 ms 106540 KB Output is correct
4 Correct 3330 ms 101260 KB Output is correct
5 Correct 4268 ms 130968 KB Output is correct
6 Correct 5090 ms 108040 KB Output is correct
7 Correct 4976 ms 43912 KB Output is correct
8 Correct 4054 ms 43884 KB Output is correct
9 Correct 4223 ms 47864 KB Output is correct
10 Correct 4735 ms 45204 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 1581 ms 26988 KB Output is correct
3 Correct 1651 ms 27024 KB Output is correct
4 Correct 1590 ms 27284 KB Output is correct
5 Correct 1527 ms 27372 KB Output is correct
6 Correct 1278 ms 27104 KB Output is correct
7 Correct 1599 ms 26988 KB Output is correct
8 Correct 1628 ms 27136 KB Output is correct
9 Correct 1527 ms 27372 KB Output is correct
10 Correct 1284 ms 27120 KB Output is correct
11 Correct 1592 ms 27104 KB Output is correct
12 Correct 14 ms 18284 KB Output is correct
13 Correct 3628 ms 103728 KB Output is correct
14 Correct 4655 ms 106540 KB Output is correct
15 Correct 3330 ms 101260 KB Output is correct
16 Correct 4268 ms 130968 KB Output is correct
17 Correct 5090 ms 108040 KB Output is correct
18 Correct 4976 ms 43912 KB Output is correct
19 Correct 4054 ms 43884 KB Output is correct
20 Correct 4223 ms 47864 KB Output is correct
21 Correct 4735 ms 45204 KB Output is correct
22 Correct 7091 ms 105896 KB Output is correct
23 Correct 6530 ms 108580 KB Output is correct
24 Correct 7956 ms 109544 KB Output is correct
25 Execution timed out 8077 ms 111408 KB Time limit exceeded
26 Halted 0 ms 0 KB -