Submission #52234

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
52234	2018-06-25 05:43:46	ics0503	Factories (JOI14_factories)	C++17	100 / 100	6914 ms	228692 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<vector>
#include<algorithm>
using namespace std;
struct xy { long long x, y; };
struct gg { int w, s, e; };
bool sort_y(xy a, xy b) {
  if (a.y != b.y)return a.y < b.y;
  return a.x < b.x;
}
vector<xy>edge[515151];
long long W[515151], ST[515151],EN[515151], Dist[515151], Depth[515151], cnt = 0;
long long par[515151][21];
bool sort_st(long long a, long long b) {
  if (ST[a] != ST[b])return ST[a] < ST[b];
  return EN[a] > EN[b];
}
void dfs(long long w, long long bef,long long depth,long long dist) {
  Depth[w] = depth;
  Dist[w] = dist;
  ST[w] = cnt;  W[w] = cnt++;
  par[w][0] = bef;
  for (long long i = 0; par[w][i] != -1; i++) par[w][i + 1] = par[par[w][i]][i];
  for (long long i = 0; i < edge[w].size(); i++) if (bef != edge[w][i].x){
    dfs(edge[w][i].x, w, depth+1, dist + edge[w][i].y);
  }
  EN[w] = cnt - 1;
}
void Init(int N, int A[], int B[], int D[]) {
  long long i, j;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (stderr)

factories.cpp: In function 'void dfs(long long int, long long int, long long int, long long int)':
factories.cpp:24:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (long long i = 0; i < edge[w].size(); i++) if (bef != edge[w][i].x){
                        ~~^~~~~~~~~~~~~~~~
factories.cpp: In function 'void DFS(int, int)':
factories.cpp:58:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (long long i = 0; i < E[w].size(); i++) {
                        ~~^~~~~~~~~~~~~
factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:69:9: warning: unused variable 'j' [-Wunused-variable]
  int i, j; ln = an = 0;
         ^

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