| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 49298 |
2018-05-25T04:54:46 Z |
wzy |
Factories (JOI14_factories) |
C++11 |
|
6000 ms |
143136 KB |
#include <bits/stdc++.h>
#include "factories.h"
using namespace std;
#define pii pair<int,long long>
#define F first
#define S second
#define pb push_back
bool jafoi[500005];
vector<pii> adj[500005] ;
int n , pai[500005] , lca[22][500005] , depth[500005] , st[500005] , t= 0 , ed[500005] ;
long long dist[500005] , dp[2][500005];
int op[1000000];
int pointer = 0;
void pre_dfs(int x , int y){
pai[x] = y;
st[x] = ++t;
for(int j = 0 ; j < adj[x].size() ; j++){
pii u = adj[x][j];
if(u.first == y) continue;
dist[u.first] = dist[x] + u.second;
depth[u.first] = depth[x] + 1;
pre_dfs(u.first, x);
}
ed[x] = t;
}
int query_lca(int x , int y){
if(depth[x] > depth[y]) swap(x,y);
for(int j = 21 ; j >= 0 ; j--){
long long u = depth[y] - (1<<j);
if(u >= depth[x]){
y = lca[j][y];
}
}
if(x == y) return x;
for(int j = 21 ; j >= 0 ; j--){
if(lca[j][x] != lca[j][y] && lca[j][x] != -1){
x = lca[j][x] , y = lca[j][y];
}
}
return pai[x];
}
void Init(int N, int A[], int B[], int D[]){
n = N;
for(int i = 0 ; i < N - 1 ; i++){
adj[A[i]].pb(pii(B[i] , D[i]));
adj[B[i]].pb(pii(A[i] , D[i]));
}
depth[0] = 0 , dist[0] = 0;
pre_dfs(0 , - 1 );
pai[0] = -1;
for(int i = 0 ; i < N ; i++){
lca[0][i] = pai[i];
}
for(int j = 1 ; j < 22 ; j++){
for(int i = 0 ; i < N ; i++){
if(lca[j-1][i] != -1)
lca[j][i] = lca[j-1][lca[j-1][i]];
}
}
for(int i = 0 ; i < N - 1; i++){
adj[A[i]].clear() , adj[B[i]].clear();
}
}
bool cmp(int a , int b){
return st[a] < st[b];
}
long long ansz = 0;
void solve(int x , int y){
for(int j = 0 ; j < adj[x].size() ; j++){
pii u = adj[x][j];
if(u.F == y) continue;
solve(u.F, x);
ansz = min(ansz , min(dp[0][x] + dp[1][u.F] + u.S , dp[1][x] + dp[0][u.F] + u.S));
dp[0][x] = min(dp[0][x] , dp[0][u.F] + u.S);
dp[1][x] = min(dp[1][x] , dp[1][u.F] + u.S);
}
return ;
}
long long Query(int S , int X[] , int T , int Y[]){
pointer = 0;
for(int i = 0 ; i < max(S,T) ;i ++){
if(!jafoi[X[i]] && i < S){
op[pointer++] = X[i];
jafoi[X[i]] = 1;
dp[0][X[i]] = 0;
dp[1][X[i]] = 1000000000000000LL;
}
if(!jafoi[Y[i]] && i < T){
op[pointer++] = Y[i];
jafoi[Y[i]] = 1;
dp[1][Y[i]] = 0;
dp[0][Y[i]] = 1000000000000000LL;
}
}
sort(op , op + pointer , cmp);
int Z = (pointer)- 1;
for(int i = 0 ; i < Z ; i++){
int L = query_lca(op[i] , op[i+1]);
if(!jafoi[L]){
dp[0][L] = 1000000000000000LL;
dp[1][L] = 1000000000000000LL;
op[pointer++] = L;
jafoi[L] = 1;
}
}
sort(op , op + pointer , cmp);
stack<int> w;
int root = op[0];
w.push(op[0]);
for(int i = 1; i < pointer ; i++){
while(w.size() && !(st[w.top()] <= st[op[i]] && st[op[i]] <= ed[w.top()])){
w.pop();
}
long long u =dist[op[i]] - dist[w.top()];
adj[op[i]].push_back(pii(w.top() , u));
adj[w.top()].push_back(pii(op[i] , u));
w.push(op[i]);
}
ansz = 1000000000000000LL;
solve(root , root);
for(int i = 0 ; i < pointer; i++){
adj[op[i]].clear();
jafoi[op[i]] = false;
}
return ansz;
}
Compilation message
factories.cpp: In function 'void pre_dfs(int, int)':
factories.cpp:17:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = 0 ; j < adj[x].size() ; j++){
~~^~~~~~~~~~~~~~~
factories.cpp: In function 'void solve(int, int)':
factories.cpp:76:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = 0 ; j < adj[x].size() ; j++){
~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
34 ms |
12664 KB |
Output is correct |
| 2 |
Correct |
1338 ms |
21484 KB |
Output is correct |
| 3 |
Correct |
1493 ms |
21704 KB |
Output is correct |
| 4 |
Correct |
1326 ms |
21704 KB |
Output is correct |
| 5 |
Correct |
1075 ms |
21772 KB |
Output is correct |
| 6 |
Correct |
1093 ms |
21772 KB |
Output is correct |
| 7 |
Correct |
1460 ms |
21772 KB |
Output is correct |
| 8 |
Correct |
1419 ms |
21772 KB |
Output is correct |
| 9 |
Correct |
1055 ms |
21884 KB |
Output is correct |
| 10 |
Correct |
1298 ms |
21884 KB |
Output is correct |
| 11 |
Correct |
1409 ms |
21884 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
21884 KB |
Output is correct |
| 2 |
Correct |
3717 ms |
114164 KB |
Output is correct |
| 3 |
Correct |
4883 ms |
116168 KB |
Output is correct |
| 4 |
Correct |
2415 ms |
116168 KB |
Output is correct |
| 5 |
Correct |
3705 ms |
134872 KB |
Output is correct |
| 6 |
Correct |
5772 ms |
134872 KB |
Output is correct |
| 7 |
Correct |
4792 ms |
134872 KB |
Output is correct |
| 8 |
Correct |
2814 ms |
134872 KB |
Output is correct |
| 9 |
Correct |
4096 ms |
134872 KB |
Output is correct |
| 10 |
Correct |
5829 ms |
134872 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5923 ms |
134872 KB |
Output is correct |
| 2 |
Correct |
5668 ms |
134872 KB |
Output is correct |
| 3 |
Execution timed out |
6081 ms |
143136 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
