oj.uz

Submission #370834

# Submission time Handle Problem Language Result Execution time Memory
370834 2021-02-24T17:56:35 Z alirezasamimi100 Factories (JOI14_factories) C++17
33 / 100
 8000 ms 131032 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){
  if(!mp[v]) dp[v]=0;
  for(auto [u,w] : adj[v]){
      DFS(u);
      dp[v]=min(dp[u]+w,dp[v]);
  }
}
void sfd(int v){
  for(auto [u,w] : adj[v]){
      dp[u]=min(dp[u],dp[v]+w);
      sfd(u);
  }
}
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={};
    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]]={};
    for(int i=1; i<z.size(); i++){
      adj[z[i]]={};
      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);
      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:123:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  123 |     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 1599 ms 27104 KB Output is correct
3 Correct 1596 ms 26964 KB Output is correct
4 Correct 1587 ms 27448 KB Output is correct
5 Correct 1525 ms 27372 KB Output is correct
6 Correct 1243 ms 27244 KB Output is correct
7 Correct 1578 ms 26988 KB Output is correct
8 Correct 1561 ms 27116 KB Output is correct
9 Correct 1514 ms 27628 KB Output is correct
10 Correct 1326 ms 27196 KB Output is correct
11 Correct 1612 ms 27068 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 3536 ms 103440 KB Output is correct
3 Correct 4563 ms 106332 KB Output is correct
4 Correct 3267 ms 101076 KB Output is correct
5 Correct 4449 ms 131032 KB Output is correct
6 Correct 5134 ms 107796 KB Output is correct
7 Correct 4574 ms 44112 KB Output is correct
8 Correct 4139 ms 43860 KB Output is correct
9 Correct 4410 ms 47840 KB Output is correct
10 Correct 4906 ms 45164 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 1599 ms 27104 KB Output is correct
3 Correct 1596 ms 26964 KB Output is correct
4 Correct 1587 ms 27448 KB Output is correct
5 Correct 1525 ms 27372 KB Output is correct
6 Correct 1243 ms 27244 KB Output is correct
7 Correct 1578 ms 26988 KB Output is correct
8 Correct 1561 ms 27116 KB Output is correct
9 Correct 1514 ms 27628 KB Output is correct
10 Correct 1326 ms 27196 KB Output is correct
11 Correct 1612 ms 27068 KB Output is correct
12 Correct 14 ms 18284 KB Output is correct
13 Correct 3536 ms 103440 KB Output is correct
14 Correct 4563 ms 106332 KB Output is correct
15 Correct 3267 ms 101076 KB Output is correct
16 Correct 4449 ms 131032 KB Output is correct
17 Correct 5134 ms 107796 KB Output is correct
18 Correct 4574 ms 44112 KB Output is correct
19 Correct 4139 ms 43860 KB Output is correct
20 Correct 4410 ms 47840 KB Output is correct
21 Correct 4906 ms 45164 KB Output is correct
22 Correct 6863 ms 105960 KB Output is correct
23 Correct 6269 ms 108324 KB Output is correct
24 Correct 7597 ms 109672 KB Output is correct
25 Correct 7755 ms 112836 KB Output is correct
26 Execution timed out 8077 ms 108596 KB Time limit exceeded
27 Halted 0 ms 0 KB -