oj.uz

Submission #386868

# Submission time Handle Problem Language Result Execution time Memory
386868 2021-04-07T14:23:53 Z uacoder123 Factories (JOI14_factories) C++14
33 / 100
 8000 ms 229896 KB 
    #include "factories.h"
    #include <bits/stdc++.h>
    #include <ext/pb_ds/assoc_container.hpp>
    using namespace std;
    using namespace __gnu_pbds;
    #define F first
    #define S second
    #define FOR(i,a,b) for (auto i = (a); i <= (b); ++i)
    #define NFOR(i,a,b) for(auto i = (a); i >= (b); --i)
    #define all(x) (x).begin(), (x).end()
    #define sz(x) lli(x.size())
    #define mp(i,a) make_pair(i,a)
    #define pb(a) push_back(a)
    #define bit(x,b) (x&(1LL<<b))
    typedef long long int lli;
    typedef pair <lli,lli> ii;
    typedef pair <ii,lli> iii;
    typedef vector <lli> vi;
    typedef tree<lli,null_type,less<lli>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
    int n;
    vector<ii> al[500001];
    lli dp[500001],par[500001][25],par1[500001],lev[500001],din[500001],dout[500001],t=0,sz[500001],vis[500001],vis1[500001],pre[500001],r;
    void dfs(int node)
    {
      sz[node]=1;
      vis1[node]=1;
      for(int i=0;i<al[node].size();++i)
      {
        if(vis1[al[node][i].F]+vis[al[node][i].F]==0)
        {
          dfs(al[node][i].F);
          sz[node]+=sz[al[node][i].F];
        }
      }
    }
    int tell(int node,int p,int to)
    {
        for(int i=0;i<al[node].size();++i)
        {
          if(al[node][i].F!=p&&sz[al[node][i].F]>to/2&&vis[al[node][i].F]==0)
            return tell(al[node][i].F,node,to);
        }
        return node;
    }
    void dfs1(int node,int p,int cen)
    {
      pre[node]=cen;
      for(int i=0;i<al[node].size();++i)
        if(al[node][i].F!=p&&vis[al[node][i].F]==0)
          dfs1(al[node][i].F,node,cen);
    }
    void dfs2(int node,int p,lli l)
    {
      par[node][0]=p;
      for(int i=1;i<25;++i)
        par[node][i]=par[par[node][i-1]][i-1];
      lev[node]=l;
      din[node]=t++;
      for(int i=0;i<al[node].size();++i)
      {
        if(al[node][i].F!=p)
          dfs2(al[node][i].F,node,l+al[node][i].S);
      }
      dout[node]=t++;
    }
    bool isa(int f,int s)
    {
      return (din[f]<=din[s])&&(dout[f]>=dout[s]);
    }
    int lca(int f,int s)
    {
      if(isa(f,s))
        return f;
      if(isa(s,f))
        return s;
      for(int i=24;i>=0;--i)
        if(!isa(par[f][i],s))
          f=par[f][i];
      return par[f][0];
    }
    void Init(int N, int A[], int B[], int D[]) 
    {
      
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
      n=N;
      for(int i=0;i<n-1;++i)
      {
        al[A[i]].pb(mp(B[i],D[i]));
        al[B[i]].pb(mp(A[i],D[i]));
      }
      dfs2(0,0,0);
      int c=0;
      while(c!=n)
      {
        for(int i=0;i<n;++i)
        {
          if(vis[i]+vis1[i]==0)
          {
            dfs(i);
            int cen=tell(i,i,sz[i]);
            par1[cen]=pre[i];
            dfs1(i,i,cen);
            c++;
            vis[cen]=1;
            if(c==1)
              r=cen;
          }
        }
        memset(vis1,0,sizeof(vis1));
      }
      for(int i=0;i<n;++i)
        dp[i]=1000000000ll*5000000;
    }
     
    long long Query(int S, int X[], int T, int Y[]) 
    {
      vi v;
      for(lli i=0;i<S;++i)
      {
      lli cur=X[i];
          while(1)
          {
            lli l=lca(X[i],cur);
            dp[cur]=min(dp[cur],lev[X[i]]+lev[cur]-2*lev[l]);
            v.pb(cur);
            if(cur==r)
              break;
            cur=par1[cur];
          }
        }
        lli ans=1000000000ll*5000000;
        for(lli i=0;i<T;++i)
        {
     
         lli cur=Y[i];
          while(1)
          {
            lli l=lca(Y[i],cur);
            ans=min(ans,dp[cur]+lev[Y[i]]+lev[cur]-2*lev[l]);
            if(cur==r)
              break;
            cur=par1[cur];
          }
        }
        while(v.size())
        {
          dp[v.back()]=1000000000ll*5000000;
          v.pop_back();
        }
      return ans;
    }

Compilation message

factories.cpp: In function 'void dfs(int)':
factories.cpp:27:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |       for(int i=0;i<al[node].size();++i)
      |                   ~^~~~~~~~~~~~~~~~
factories.cpp: In function 'int tell(int, int, int)':
factories.cpp:38:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |         for(int i=0;i<al[node].size();++i)
      |                     ~^~~~~~~~~~~~~~~~
factories.cpp: In function 'void dfs1(int, int, int)':
factories.cpp:48:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |       for(int i=0;i<al[node].size();++i)
      |                   ~^~~~~~~~~~~~~~~~
factories.cpp: In function 'void dfs2(int, int, lli)':
factories.cpp:59:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |       for(int i=0;i<al[node].size();++i)
      |                   ~^~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 16492 KB Output is correct
2 Correct 641 ms 25892 KB Output is correct
3 Correct 1095 ms 26044 KB Output is correct
4 Correct 1068 ms 26644 KB Output is correct
5 Correct 720 ms 26388 KB Output is correct
6 Correct 304 ms 25836 KB Output is correct
7 Correct 1083 ms 26092 KB Output is correct
8 Correct 1034 ms 25984 KB Output is correct
9 Correct 711 ms 26472 KB Output is correct
10 Correct 308 ms 25756 KB Output is correct
11 Correct 1030 ms 25708 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 16364 KB Output is correct
2 Correct 4359 ms 183676 KB Output is correct
3 Correct 6947 ms 186752 KB Output is correct
4 Correct 1122 ms 181448 KB Output is correct
5 Correct 7883 ms 229896 KB Output is correct
6 Correct 7372 ms 206668 KB Output is correct
7 Correct 3488 ms 72172 KB Output is correct
8 Correct 550 ms 72156 KB Output is correct
9 Correct 3002 ms 76480 KB Output is correct
10 Correct 3621 ms 73664 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 16492 KB Output is correct
2 Correct 641 ms 25892 KB Output is correct
3 Correct 1095 ms 26044 KB Output is correct
4 Correct 1068 ms 26644 KB Output is correct
5 Correct 720 ms 26388 KB Output is correct
6 Correct 304 ms 25836 KB Output is correct
7 Correct 1083 ms 26092 KB Output is correct
8 Correct 1034 ms 25984 KB Output is correct
9 Correct 711 ms 26472 KB Output is correct
10 Correct 308 ms 25756 KB Output is correct
11 Correct 1030 ms 25708 KB Output is correct
12 Correct 17 ms 16364 KB Output is correct
13 Correct 4359 ms 183676 KB Output is correct
14 Correct 6947 ms 186752 KB Output is correct
15 Correct 1122 ms 181448 KB Output is correct
16 Correct 7883 ms 229896 KB Output is correct
17 Correct 7372 ms 206668 KB Output is correct
18 Correct 3488 ms 72172 KB Output is correct
19 Correct 550 ms 72156 KB Output is correct
20 Correct 3002 ms 76480 KB Output is correct
21 Correct 3621 ms 73664 KB Output is correct
22 Correct 5551 ms 217548 KB Output is correct
23 Correct 5959 ms 226000 KB Output is correct
24 Execution timed out 8068 ms 227316 KB Time limit exceeded
25 Halted 0 ms 0 KB -