| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 49301 |
2018-05-25T06:40:39 Z |
wzy |
Factories (JOI14_factories) |
C++11 |
|
1785 ms |
226816 KB |
#include <bits/stdc++.h>
#include "factories.h"
using namespace std;
#define ll long long
#define pil pair<int, ll>
#define F first
#define S second
#define mp make_pair
#define pb push_back
int lca[22][500005] , st[500005] , ed[500005] , depth[500005] , t=0;
ll dist[500005] , dp[2][500005];
vector<pil> adj[500005];
bool one[500005];
bool inside(int x , int y){
return (st[x] <= st[y] && ed[x] >= ed[y]);
}
int get_lca(int x , int y){
if(inside(x,y)) return x;
if(inside(y,x)) return y;
for(int j = 21 ; j >= 0 ; j--){
if(!inside(lca[j][x] , y)) x = lca[j][x];
}
return lca[0][x];
}
void compute(int x , int y){
lca[0][x] = y;
st[x] = ++t;
for(int j = 1 ; j < 22 ; j++){
lca[j][x] = lca[j-1][lca[j-1][x]];
}
for(int j = 0 ; j < adj[x].size() ; j++){
pil u = adj[x][j];
if(u.first == y) continue;
depth[u.first] = depth[x] + 1;
dist[u.first] = u.second + dist[x];
compute(u.first, x);
}
ed[x] = t;
}
void Init(int N, int A[], int B[], int D[]){
for(int i = 0 ; i < N - 1 ; i++){
adj[A[i]].push_back(pil(B[i] , D[i]));
adj[B[i]].push_back(pil(A[i] , D[i]));
}
depth[0] = 0 , dist[0] = 0LL;
compute(0 , 0);
for(int i = 0 ; i < N ; i++){
adj[A[i]].clear();
adj[B[i]].clear();
}
}
bool cmp(int a , int b){
return st[a] < st[b];
}
ll ans;
void solve(int x , int y){
for(auto u : adj[x]){
if(u.first == y) continue;
solve(u.first , x);
ans = min(ans , dp[0][x] + dp[1][u.first] + u.second);
ans = min(ans , dp[1][x] + dp[0][u.first] + u.second);
dp[0][x] = min(dp[0][x] , dp[0][u.first] + u.second);
dp[1][x] = min(dp[1][x] , dp[1][u.first] + u.second);
}
}
ll Query(int S, int X[], int T, int Y[]){
vector<int> optimal;
for(int i = 0 ; i < S ; i++){
if(!one[X[i]]){
optimal.push_back(X[i]);
one[X[i]] = 1;
dp[0][X[i]] = 0;
dp[1][X[i]] = (ll) 1e16;
}
}
for(int i = 0 ; i < T ; i++){
if(!one[Y[i]]){
optimal.push_back(Y[i]);
one[Y[i]] = 1;
dp[0][Y[i]] = (ll) 1e16;
dp[1][Y[i]] = 0;
}
}
sort(optimal.begin() , optimal.end() , cmp);
int Z = optimal.size();
for(int i = 0 ; i < Z - 1 ; i++){
int L = get_lca(optimal[i] , optimal[i+1]);
if(!one[L]){
optimal.push_back(get_lca(optimal[i] , optimal[i+1]));
one[L] = 1;
dp[0][L] = (ll) 1e16;
dp[1][L] = (ll) 1e16;
}
}
sort(optimal.begin() , optimal.end() , cmp);
stack<int> sweepline;
int root = optimal[0];
sweepline.push(optimal[0]);
for(int i = 1 ; i < optimal.size() ; i++){
one[optimal[i]] = false;
while(!inside(sweepline.top() , optimal[i])){
sweepline.pop();
}
adj[optimal[i]].push_back(pil(sweepline.top() , dist[optimal[i]] - dist[sweepline.top()]));
adj[sweepline.top()].push_back(pil(optimal[i] , dist[optimal[i]] - dist[sweepline.top()]));
sweepline.push(optimal[i]);
}
ans = (ll) 1e16;
solve(root, root);
for(int i = 0 ; i < optimal.size() ; i++) adj[optimal[i]].clear();
return ans;
}
Compilation message
factories.cpp: In function 'void compute(int, int)':
factories.cpp:31:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = 0 ; j < adj[x].size() ; j++){
~~^~~~~~~~~~~~~~~
factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:103:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 1 ; i < optimal.size() ; i++){
~~^~~~~~~~~~~~~~~~
factories.cpp:114:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0 ; i < optimal.size() ; i++) adj[optimal[i]].clear();
~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
30 ms |
24952 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
28 ms |
24952 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1785 ms |
226816 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
