Submission #56997

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
56997	2018-07-13 13:09:13	RezwanArefin01	Factories (JOI14_factories)	C++17	100 / 100	7537 ms	247096 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 <bits/stdc++.h>
#include "factories.h"
using namespace std;
typedef long long ll; 
const int MAX = 5e5 + 10; 
vector<int> adj[MAX], cost[MAX]; 
int lvl[MAX], sub[MAX], p[MAX], vis[MAX];
ll d[20][MAX], ans[MAX];
  
void calc(int u, int par) { sub[u] = 1; 
  for(int v : adj[u]) if(v - par && !vis[v]) 
    calc(v, u), sub[u] += sub[v];
}
int centroid(int u, int par, int r) {
  for(int v : adj[u]) if(v - par && !vis[v]) 
    if(sub[v] > r) return centroid(v, u, r);
  return u;
}
void dfs(int l, int u, int par, int pcost) {
  if(par + 1) d[l][u] = d[l][par] + pcost; 
  for(int i = 0; i < adj[u].size(); i++) {
    int v = adj[u][i], c = cost[u][i]; 
    if(v == par || vis[v]) continue; 
    dfs(l, v, u, c); 
  }
}
void decompose(int u, int par) {
  calc(u, -1);
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (stderr)

factories.cpp: In function 'void dfs(int, int, int, int)':
factories.cpp:23:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < adj[u].size(); i++) {
                 ~~^~~~~~~~~~~~~~~

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