| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 49282 |
2018-05-24T19:46:37 Z |
wzy |
Factories (JOI14_factories) |
C++11 |
|
6000 ms |
232508 KB |
#include <bits/stdc++.h>
#include "factories.h"
using namespace std;
#define pii pair<int,int>
#define F first
#define S second
#define pb push_back
vector<pii> adj[500005] , vt[500005];
int n , pai[500005] , lca[22][500005] , depth[500005] , st[500005] , t= 0 , ed[500005] ;
long long dist[500005] , dp[2][500005];
bool fs[500005] , ss[500005];
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--){
int 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];
}
long long distance_query(int x , int y){
return dist[x] + dist[y] - 2*dist[query_lca(x,y)];
}
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 );
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++){
lca[j][i] = lca[j-1][lca[j-1][i]];
}
}
}
bool cmp(pii a , pii b){
if(st[a.F] == st[b.F]) return a.S < b.S;
return st[a.F] < st[b.F];
}
long long ansz = 0;
void solve(int x , int y){
for(int j = 0 ; j <vt[x].size() ; j++){
pii u = vt[x][j];
if(u.first == y) continue;
solve(u.first , x);
dp[0][x] = min(dp[0][x] , u.second + dp[0][u.first]);
dp[1][x] = min(dp[1][x] , u.second + dp[1][u.first]);
}
long long maxA = (long long) 1e18 , maxB = (long long) 1e18;
if(fs[x]) maxA = 0;
if(ss[x]) maxB = 0;
for(int j = 0 ; j < vt[x].size() ; j++){
pii u = vt[x][j];
if(u.first == y) continue;
ansz = min(ansz , dp[0][u.first] + maxB + u.second);
ansz = min(ansz , dp[1][u.first] + maxA + u.second);
maxA = min(maxA , dp[0][u.first] + u.second);
maxB = min(maxB , dp[1][u.first] + u.second);
}
if(fs[x]) ansz = min(ansz , dp[1][x]);
if(ss[x]) ansz = min(ansz , dp[0][x]);
return ;
}
long long Query(int S , int X[] , int T , int Y[]){
vector<pii> v;
for(int i = 0 ; i < S ;i ++){
v.pb(pii(X[i] , 0));
}
for(int i = 0 ; i < T ;i ++){
v.pb(pii(Y[i] , 1));
}
sort(v.begin() , v.end() , cmp);
vector<pii> op;
set<int> u;
for(int i = 0 ; i < v.size() ; i++){
if(!u.count(v[i].F)){
op.push_back(v[i]);
u.insert(v[i].F);
}
}
for(int i = 0 ; i < ((int)v.size()) - 1 ; i++){
if(!u.count(query_lca(v[i].F , v[i+1].F))){
op.push_back(pii(query_lca(v[i].F , v[i+1].F) , 3));
u.insert(query_lca(v[i].F , v[i+1].F));
}
}
sort(op.begin() , op.end() ,cmp);
for(int i = 0 ; i < op.size() ; i++){
if(op[i].second == 0){
fs[op[i].first] = 1;
}
else if(op[i].second == 1){
ss[op[i].first] = 1 ;
}
}
stack<int> w;
int root = 0;
for(int i = 0 ; i < op.size() ; i++){
dp[0][op[i].first] = (long long) 1e18;
dp[1][op[i].first] = (long long) 1e18;
if(w.empty()) w.push(op[i].first) , root = op[i].first;
else{
while(w.size() && !(st[w.top()] <= st[op[i].first] && st[op[i].first] <= ed[w.top()])){
w.pop();
}
vt[op[i].first].push_back(pii(w.top() , distance_query(w.top() , op[i].first)));
vt[w.top()].push_back(pii(op[i].first , distance_query(w.top() , op[i].first)));
w.push(op[i].first);
}
}
for(int i = 0 ; i < op.size() ; i++){
if(fs[op[i].first]) dp[0][op[i].first] = 0;
if(ss[op[i].first]) dp[1][op[i].first] = 0;
}
ansz = (long long) 1e18;
solve(root , root);
for(int i = 0 ; i < op.size() ; i++){
vt[op[i].first].clear();
if(op[i].second == 0){
fs[op[i].first] = 0;
}
else if(op[i].second == 1){
ss[op[i].first] = 0 ;
}
}
return ansz;
}
Compilation message
factories.cpp: In function 'void pre_dfs(int, int)':
factories.cpp:16:20: 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:74:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = 0 ; j <vt[x].size() ; j++){
~~^~~~~~~~~~~~~
factories.cpp:84:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = 0 ; j < vt[x].size() ; j++){
~~^~~~~~~~~~~~~~
factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:108:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0 ; i < v.size() ; i++){
~~^~~~~~~~~~
factories.cpp:121:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0 ; i < op.size() ; i++){
~~^~~~~~~~~~~
factories.cpp:131:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0 ; i < op.size() ; i++){
~~^~~~~~~~~~~
factories.cpp:144:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0 ; i < op.size() ; i++){
~~^~~~~~~~~~~
factories.cpp:150:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0 ; i < op.size() ; i++){
~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
86 ms |
24824 KB |
Output is correct |
| 2 |
Correct |
2703 ms |
43220 KB |
Output is correct |
| 3 |
Correct |
3108 ms |
52780 KB |
Output is correct |
| 4 |
Incorrect |
2618 ms |
62480 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
26 ms |
62480 KB |
Output is correct |
| 2 |
Correct |
4182 ms |
181800 KB |
Output is correct |
| 3 |
Execution timed out |
6085 ms |
198556 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
6108 ms |
232508 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
