# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
339693 |
2020-12-25T23:36:07 Z |
gmyu |
Factories (JOI14_factories) |
C++14 |
|
8000 ms |
268200 KB |
/*
ID: USACO_template
LANG: C++
PROG: https://oj.uz/problem/view/JOI14_factories
*/
#include <iostream> //cin , cout
#include <fstream> //fin, fout
#include <stdio.h> // scanf , pringf
#include <cstdio>
#include <algorithm> // sort , stuff
#include <stack> // stacks
#include <queue> // queues
#include <map>
#include <string>
#include <set>
#include "factories.h"
using namespace std;
typedef pair<int, int> pii;
typedef vector<int> vi; /// adjlist without weight
typedef vector<pii> vii; /// adjlist with weight
typedef vector<pair<int,pii>> vpip; /// edge with weight
typedef long long ll;
#define mp make_pair
#define fst first
#define snd second
#define pb push_back
#define sz(x) (int)(x).size()
#define trav(u, adj_v) for (auto& u: adj_v)
const int MOD = 1e9+7; // 998244353;
const int MX = 2e5+5; //
const ll INF = 1e18; //
#define MAXV 500007
#define MAXE 100007
bool debug;
int N, Q;
vi adjlist[MAXV];
map<int, ll> adjmap[MAXV];
struct NODE {
vector<int> cenlist; /// list of centroid ID for each node
vector<ll> cenDist; /// corresponding distance of node to each centroid
int subtreeSize;
};
NODE nodes[MAXV];
/// centroid property
struct CENTR {
int from; /// the original point for centroid is from (child of upper level centroid)
ll mdist; /// shortest distance from red to this centriod
bool visited;
};
CENTR cents[MAXV];
int dfs_size(int cur, int parent) {
nodes[cur].subtreeSize = 1;
for (int v : adjlist[cur])
if (v != parent && !cents[v].visited)
nodes[cur].subtreeSize += dfs_size(v, cur);
return nodes[cur].subtreeSize;
}
int find_cent(int cur, int parent, int cenSize) {
for (int v : adjlist[cur])
if (v != parent && !cents[v].visited)
if (nodes[v].subtreeSize * 2 > cenSize) // not using >=, keep centroid close to top
return find_cent(v, cur, cenSize);
return cur;
}
static void dfs_depth(int cur, int parent, int cid, ll depth) {
nodes[cur].cenlist.pb(cid);
nodes[cur].cenDist.pb(depth);
for (int v : adjlist[cur])
if (v != parent && !cents[v].visited)
dfs_depth(v, cur, cid, depth + adjmap[cur][v]);
}
void buildCentriod(int top, int parent) {
/// find centriod
dfs_size(top, parent);
int c = find_cent(top, parent, nodes[top].subtreeSize);
cents[c].from = top; cents[c].mdist = INF;
cents[c].visited = true;
/// assign tree behavior relative to this centroid
dfs_depth(c, 0, c, 0LL);
/// dfs, NlgN complexity
for (int v : adjlist[c])
if (!cents[v].visited) buildCentriod(v, c);
}
void Init(int _N, int A[], int B[], int D[]) {
N = _N;
for(int i=0; i<N-1; i++) {
int u = A[i]+1, v = B[i]+1; ll w = D[i];
adjlist[u].pb(v); adjlist[v].pb(u);
adjmap[u][v] = w; adjmap[v][u] = w;
}
buildCentriod(1, 0);
}
long long Query(int S, int X[], int T, int Y[]) {
for(int i=1; i<=N; i++) cents[i].mdist = INF;
for(int i=0; i<S; i++) {
int a = X[i] + 1;
for(int j = 0; j < sz(nodes[a].cenlist); j++) {
int c = nodes[a].cenlist[j];
ll w = nodes[a].cenDist[j];
cents[c].mdist = min(cents[c].mdist, w);
}
}
ll ret = INF;
for(int i=0; i<T; i++) {
int a = Y[i] + 1;
for(int j = 0; j < sz(nodes[a].cenlist); j++) {
int c = nodes[a].cenlist[j];
ll w = nodes[a].cenDist[j] + cents[c].mdist;
ret = min(ret, w);
}
}
return ret;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
47 ms |
63468 KB |
Output is correct |
2 |
Correct |
421 ms |
72940 KB |
Output is correct |
3 |
Correct |
432 ms |
73452 KB |
Output is correct |
4 |
Correct |
419 ms |
73580 KB |
Output is correct |
5 |
Correct |
445 ms |
73964 KB |
Output is correct |
6 |
Correct |
357 ms |
72844 KB |
Output is correct |
7 |
Correct |
437 ms |
73040 KB |
Output is correct |
8 |
Correct |
435 ms |
73068 KB |
Output is correct |
9 |
Correct |
445 ms |
73516 KB |
Output is correct |
10 |
Correct |
353 ms |
72300 KB |
Output is correct |
11 |
Correct |
426 ms |
73068 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
43 ms |
63360 KB |
Output is correct |
2 |
Execution timed out |
8048 ms |
268200 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
47 ms |
63468 KB |
Output is correct |
2 |
Correct |
421 ms |
72940 KB |
Output is correct |
3 |
Correct |
432 ms |
73452 KB |
Output is correct |
4 |
Correct |
419 ms |
73580 KB |
Output is correct |
5 |
Correct |
445 ms |
73964 KB |
Output is correct |
6 |
Correct |
357 ms |
72844 KB |
Output is correct |
7 |
Correct |
437 ms |
73040 KB |
Output is correct |
8 |
Correct |
435 ms |
73068 KB |
Output is correct |
9 |
Correct |
445 ms |
73516 KB |
Output is correct |
10 |
Correct |
353 ms |
72300 KB |
Output is correct |
11 |
Correct |
426 ms |
73068 KB |
Output is correct |
12 |
Correct |
43 ms |
63360 KB |
Output is correct |
13 |
Execution timed out |
8048 ms |
268200 KB |
Time limit exceeded |
14 |
Halted |
0 ms |
0 KB |
- |