Submission #372219

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
372219	2021-02-27 09:36:18	MahdiBahramian	Factories (JOI14_factories)	C++11	100 / 100	4046 ms	121800 KiB

factories

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include "factories.h"
#include<bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define F first
#define S second
#define mp make_pair
#define pb push_back
typedef long long ll;
using namespace std;
const int Max = 5e5 + 10;
const int LOG = 20;
const ll INF = 1e17 + 10;
int n;
vector<pair<int , int>> N[Max];
int sttime[Max] , edtime[Max] , ttime , par[Max][LOG] , h[Max];
ll dst[Max];
void DFS(int v , int p = 0)
{
  sttime[v] = ++ttime;
  for(int lg = 1 ; lg < LOG ; lg++) par[v][lg] = par[par[v][lg - 1]][lg - 1];
  for(pair<int , int> u : N[v]) if(u.F != p) h[u.F] = h[v] + 1 , par[u.F][0] = v , dst[u.F] = dst[v] + u.S , DFS(u.F , v);
  edtime[v] = ttime + 1;
}
int lca(int a , int b)
{
  //if(a == b) return a;
  if(h[a] < h[b]) swap(a , b);
  for(int lg = LOG ; lg-- ; ) if((h[a] - h[b]) & (1 << lg)) a = par[a][lg];
  if(a == b) return a;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (stderr)

factories.cpp: In function 'void dfs(std::vector<int>&)':
factories.cpp:46:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |  for(int i = 1 ; i < verts.size() ; i++)
      |                  ~~^~~~~~~~~~~~~~
factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:72:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |  for(int i = 0 ; i < srt1.size() - 1 ; i++)
      |                  ~~^~~~~~~~~~~~~~~~~

• Subtask 1: 15 / 15
• Subtask 2: 18 / 18
• Subtask 3: 67 / 67