oj.uz

Submission #389684

# Submission time Handle Problem Language Result Execution time Memory
389684 2021-04-14T11:27:14 Z uacoder123 Factories (JOI14_factories) C++14
100 / 100
 7821 ms 296452 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][20],par1[500001],lev[500001],din[500001],dout[500001],t=0,sz[500001],vis[500001],vis1[500001],pre[500001],r;
        lli dist[5*100001][20];
        lli lev1[5*100001];
        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,lli l)
        {
          pre[node]=cen;
          dist[node][lev1[cen]]=l;
          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,l+al[node][i].S);
        }
        void dfs2(int node,int p,lli l)
        {
          par[node][0]=p;
          for(int i=1;i<20;++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=19;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,xy=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];
                lev1[cen]=xy;
                dfs1(cen,cen,cen,0);
                c++;
                vis[cen]=1;
                if(c==1)
                  r=cen;
              }
            }
            memset(vis1,0,sizeof(vis1));
            xy++;
          }
          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)
              {
        dp[cur]=min(dp[cur],dist[X[i]][lev1[cur]]);
                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)
              {
                ans=min(ans,dp[cur]+dist[Y[i]][lev1[cur]]);
                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:32:24: 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]
   32 |           for(int i=0;i<al[node].size();++i)
      |                       ~^~~~~~~~~~~~~~~~
factories.cpp: In function 'int tell(int, int, int)':
factories.cpp:43:26: 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]
   43 |             for(int i=0;i<al[node].size();++i)
      |                         ~^~~~~~~~~~~~~~~~
factories.cpp: In function 'void dfs1(int, int, int, lli)':
factories.cpp:54:24: 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]
   54 |           for(int i=0;i<al[node].size();++i)
      |                       ~^~~~~~~~~~~~~~~~
factories.cpp: In function 'void dfs2(int, int, lli)':
factories.cpp:65:24: 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]
   65 |           for(int i=0;i<al[node].size();++i)
      |                       ~^~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 16588 KB Output is correct
2 Correct 399 ms 28420 KB Output is correct
3 Correct 407 ms 27972 KB Output is correct
4 Correct 436 ms 28928 KB Output is correct
5 Correct 447 ms 28624 KB Output is correct
6 Correct 289 ms 28132 KB Output is correct
7 Correct 421 ms 27996 KB Output is correct
8 Correct 436 ms 28108 KB Output is correct
9 Correct 455 ms 28660 KB Output is correct
10 Correct 277 ms 28044 KB Output is correct
11 Correct 414 ms 28024 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 16332 KB Output is correct
2 Correct 3500 ms 246404 KB Output is correct
3 Correct 5447 ms 249428 KB Output is correct
4 Correct 1116 ms 243996 KB Output is correct
5 Correct 6917 ms 273684 KB Output is correct
6 Correct 5496 ms 250608 KB Output is correct
7 Correct 1369 ms 72024 KB Output is correct
8 Correct 572 ms 71740 KB Output is correct
9 Correct 1630 ms 76484 KB Output is correct
10 Correct 1413 ms 73148 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 16588 KB Output is correct
2 Correct 399 ms 28420 KB Output is correct
3 Correct 407 ms 27972 KB Output is correct
4 Correct 436 ms 28928 KB Output is correct
5 Correct 447 ms 28624 KB Output is correct
6 Correct 289 ms 28132 KB Output is correct
7 Correct 421 ms 27996 KB Output is correct
8 Correct 436 ms 28108 KB Output is correct
9 Correct 455 ms 28660 KB Output is correct
10 Correct 277 ms 28044 KB Output is correct
11 Correct 414 ms 28024 KB Output is correct
12 Correct 13 ms 16332 KB Output is correct
13 Correct 3500 ms 246404 KB Output is correct
14 Correct 5447 ms 249428 KB Output is correct
15 Correct 1116 ms 243996 KB Output is correct
16 Correct 6917 ms 273684 KB Output is correct
17 Correct 5496 ms 250608 KB Output is correct
18 Correct 1369 ms 72024 KB Output is correct
19 Correct 572 ms 71740 KB Output is correct
20 Correct 1630 ms 76484 KB Output is correct
21 Correct 1413 ms 73148 KB Output is correct
22 Correct 4043 ms 255844 KB Output is correct
23 Correct 4212 ms 263832 KB Output is correct
24 Correct 6123 ms 265520 KB Output is correct
25 Correct 6438 ms 284576 KB Output is correct
26 Correct 6240 ms 255716 KB Output is correct
27 Correct 7821 ms 296452 KB Output is correct
28 Correct 1372 ms 249784 KB Output is correct
29 Correct 6319 ms 251512 KB Output is correct
30 Correct 6143 ms 250924 KB Output is correct
31 Correct 6134 ms 251356 KB Output is correct
32 Correct 1843 ms 98096 KB Output is correct
33 Correct 609 ms 82500 KB Output is correct
34 Correct 1077 ms 79016 KB Output is correct
35 Correct 1062 ms 78940 KB Output is correct
36 Correct 1391 ms 79772 KB Output is correct
37 Correct 1311 ms 79772 KB Output is correct