| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 52214 |
2018-06-25T05:03:45 Z |
이창수(#1964) |
Factories (JOI14_factories) |
C++11 |
|
6000 ms |
655360 KB |
#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;
for (i = 0; i < N-1; i++) {
long long s = A[i], e = B[i], w = D[i];
edge[s].push_back({ e,w }); edge[e].push_back({ s,w });
}
for (i = 0; i < N; i++)for (j = 0; j < 20; j++)par[i][j] = -1;
dfs(0, -1, 0, 0);
}
xy L[512121]; long long ln;
gg Q[515151];
long long ALL[515151], an;
void go(long long &x, long long y) { for (long long i = 0; i < 20; i++)if (y&(1 << i))x = par[x][i]; }
long long LCA(long long a, long long b) {
if (Depth[a] > Depth[b])go(a, Depth[a] - Depth[b]);
if (Depth[a] < Depth[b])go(b, Depth[b] - Depth[a]);
if (a == b)return a;
for (long long i = 19; i >= 0; i--)if (par[a][i] != par[b][i])a = par[a][i], b = par[b][i];
return par[a][0];
}
long long P[515151];
vector<xy>E[515151];
long long D[515151], F[515151], CR[515151];
long long res;
long long min(long long a, long long b) { if (a < b)return a; return b; }
void DFS(int w,int bef) {
D[w] = F[w] = 1e18;
if (CR[w] == 1)D[w] = 0;
if (CR[w] == 2)F[w] = 0;
for (long long i = 0; i < E[w].size(); i++) {
int nxt = E[w][i].x;
if (nxt == bef)continue;
DFS(nxt, w);
D[w] = min(D[w], D[nxt] + E[w][i].y);
F[w] = min(F[w], F[nxt] + E[w][i].y);
}
res = min(res, D[w] + F[w]);
}
long long Query(int S, int X[], int T, int Y[]){
res = 1e18;
int i, j; ln = an = 0;
for (i = 0; i < S; i++)L[ln++] = { X[i],W[X[i]] }, ALL[an++] = X[i], CR[X[i]] = 1;
for (i = 0; i < T; i++)L[ln++] = { Y[i],W[Y[i]] }, ALL[an++] = Y[i], CR[Y[i]] = 2;
sort(L, L + ln,sort_y);
for (i = 0; i < ln-1; i++) ALL[an++] = LCA(L[i].x, L[i+1].x);
sort(ALL, ALL + an, sort_st);
an = unique(ALL, ALL + an) - ALL;
vector<int>stk;
stk.push_back(ALL[0]);
for (i = 1; i < an; i++) {
int now = ALL[i];
while (EN[stk.back()] < ST[now])stk.pop_back();
P[i] = stk.back();
stk.push_back(now);
}
for (i = 1; i < an; i++) {
long long s = ALL[i], e = P[i], w = Dist[s] - Dist[e];
E[s].push_back({ e,w });
E[e].push_back({ s,w });
}
DFS(ALL[0], -1);
for (i = 0; i < an; i++) {
while (E[ALL[i]].empty())E[ALL[i]].pop_back();
CR[ALL[i]] = 0;
}
return res;
}
Compilation message
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;
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
6114 ms |
655360 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
6155 ms |
655360 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
6114 ms |
655360 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
