| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 50739 |
2018-06-13T06:30:46 Z |
wzy |
Factories (JOI14_factories) |
C++11 |
|
6000 ms |
189496 KB |
#include"factories.h"
#include <bits/stdc++.h>
using namespace std;
/*
MAGIA DO GATINHO
PARA FAZER SEU CODE
PASSAR NO JUDGEZINHO
∧＿∧
（｡･ω･｡)つ━☆・*。
⊂ ノ ・゜+.
しーＪ °。+ *´¨)
.• ´¸.•*´¨) ¸.•*¨)
(¸.•´ (¸.•'* ☆
*/
long long dist[500005] , dp[2][500005] , depth[500005];
int st[500005] , ed[500005] , lca[22][500005] , n , T = 0;
vector<pair<int,int> > adj[500005];
void dfs(int x , int y){
st[x] = ++T;
if(x!=y) lca[0][x] = y;
for(int j = 1 ; j < 22 ; j++){
if(lca[j-1][x] != -1){
lca[j][x] = lca[j-1][lca[j-1][x]];
}
}
for(int i = 0 ; i < adj[x].size() ; i++){
if(adj[x][i].first == y) continue;
depth[adj[x][i].first] = depth[x] + 1;
dist[adj[x][i].first] = dist[x] + adj[x][i].second;
dfs(adj[x][i].first, x);
}
ed[x] = T;
}
bool inside(int x , int y){ // olha se y ta na subtree de x
return (st[x] <= st[y] && ed[x] >= ed[y]);
}
int lcaQ(int x , int y){
if(inside(x,y)) return x;
else if(inside(y,x)) return y;
for(int j = 21 ; j >= 0 ; j--){
if(lca[j][x] != - 1 && !inside(lca[j][x] , y)) x = lca[j][x];
}
return lca[0][x];
}
long long ansz = 0;
long long get_dist(int x , int y){
long long ans = dist[x] + dist[y] - 2*dist[lcaQ(x,y)];
return ans;
}
void Init(int N, int A[], int B[], int D[]){
n = N;
T = 0 ;
for(int i = 0 ; i < N ; i ++){
adj[i].clear();
}
for(int i = 0 ; i < n - 1; i ++){
adj[A[i]].push_back(pair<int,int>(B[i] , D[i]));
adj[B[i]].push_back(pair<int,int>(A[i] , D[i]));
}
for(int i = 0; i < n ; i++)
for(int j = 0 ; j < 22 ; j++) lca[j][i] = -1;
dist[0] = 0;
dfs(0 , 0 );
}
bool fl = 0;
vector<pair<int, int> > v_tree[500005];
bool cmp(int a , int b){
return st[a] < st[b];
}
bool vis[500005];
void solve(int x , int y){
vis[x] = true;
for(auto p : v_tree[x]){
if(vis[p.first]) continue;
solve(p.first, x);
ansz = min(ansz , min(dp[0][x] + dp[1][p.first] + p.second , dp[1][x] + dp[0][p.first] + p.second));
dp[0][x] = min(dp[0][x] , dp[0][p.first] + p.second);
dp[1][x] = min(dp[1][x] , dp[1][p.first] + p.second);
}
}
long long Query(int S, int X[], int T, int Y[]){
vector<int> sweep;
vector<int> loltree;
for(int i = 0 ; i < S ; i ++){
sweep.push_back(X[i]);
loltree.push_back(X[i]);
}for(int i = 0 ; i < T ; i ++){
sweep.push_back(Y[i]);
loltree.push_back(Y[i]);
}
sort(sweep.begin() , sweep.end() , cmp);
for(int i = 0 ; i < ((int)sweep.size()) - 1 ; i++){
loltree.push_back(lcaQ(sweep[i] , sweep[i+1]));
}
sort(loltree.begin() , loltree.end());
loltree.resize(unique(loltree.begin() , loltree.end()) - loltree.begin());
sort(loltree.begin() , loltree.end() , cmp);
for(int i = 0 ; i < loltree.size() ; i++){
dp[0][loltree[i]] = (long long) 1e18;
dp[1][loltree[i]] = (long long) 1e18;
}
for(int i = 0 ; i < S ;i ++){
dp[0][X[i]] = 0;
}
for(int i = 0 ; i < T ; i++){
dp[1][Y[i]] = 0;
}
int root = loltree.front();
vector<int> sline;
sline.push_back(root);
for(int i = 1 ; i < loltree.size() ; i++){
while(!inside(sline.back() , loltree[i])) sline.pop_back();
v_tree[sline.back()].push_back(pair<int,int>(loltree[i] , get_dist(loltree[i] , sline.back())));
v_tree[loltree[i]].push_back(pair<int,int>(sline.back() , get_dist(loltree[i] , sline.back())));
sline.push_back(loltree[i]);
}
ansz = (long long) 1e18;
solve(root, root);
for(int i = 0 ; i < loltree.size() ; i++){
v_tree[loltree[i]].clear();
vis[loltree[i]] = false;
}
return ansz;
}
Compilation message
factories.cpp: In function 'void dfs(int, int)':
factories.cpp:30:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0 ; i < adj[x].size() ; i++){
~~^~~~~~~~~~~~~~~
factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:115:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0 ; i < loltree.size() ; i++){
~~^~~~~~~~~~~~~~~~
factories.cpp:128:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 1 ; i < loltree.size() ; i++){
~~^~~~~~~~~~~~~~~~
factories.cpp:136:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0 ; i < loltree.size() ; i++){
~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
46 ms |
24440 KB |
Output is correct |
| 2 |
Correct |
1323 ms |
33512 KB |
Output is correct |
| 3 |
Correct |
1657 ms |
33512 KB |
Output is correct |
| 4 |
Incorrect |
1512 ms |
33564 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
25 ms |
33564 KB |
Output is correct |
| 2 |
Correct |
2814 ms |
133444 KB |
Output is correct |
| 3 |
Incorrect |
5091 ms |
133652 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5717 ms |
139376 KB |
Output is correct |
| 2 |
Correct |
5103 ms |
164572 KB |
Output is correct |
| 3 |
Execution timed out |
6088 ms |
189496 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
