| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 6772 |
2014-07-06T04:53:17 Z |
cki86201 |
오두막집 (GA7_cabana) |
C++ |
|
6000 ms |
12260 KB |
#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<vector>
#include<math.h>
#include<stdlib.h>
#include<set>
#include<ctype.h>
using namespace std;
#define X first
#define Y second
typedef long long ll;
typedef pair<int,int> Pi;
#define is_red(x) ((x) && ((x)->red==1))
const int N_ = 100010;
int n, m;
ll K;
int st[N_], en[N_<<1], nxt[N_<<1], len[N_<<1];
inline void addE(int s,int e,int l,int c){nxt[c]=st[s],st[s]=c,en[c]=e,len[c]=l;}
int is[N_], down[N_];
int cut[N_];
int MIN = 1e8;
struct node{
node(){}
node(int data,int sz):data(data),red(1),sz(sz){link[0]=link[1]=0;}
int red, data, sz;
node *link[2];
}*Root;
inline int get_size(node *tr){return tr?tr->sz:0;}
inline void update(node *tr){tr->sz = get_size(tr->link[0]) + get_size(tr->link[1]) + 1;}
node *rotate1(node *root,int dir)
{
node *save = root->link[!dir];
root->link[!dir] = save->link[dir];
save->link[dir] = root;
root->red = 1;
save->red = 0;
update(root);
update(save);
return save;
}
node *rotate2(node *root,int dir)
{
root->link[!dir] = rotate1(root->link[!dir],!dir);
return rotate1(root,dir);
}
node *rb_insert(node *root,int data)
{
if(!root)root = new node(data, 1);
else{
int dir = root->data < data;
root->link[dir] = rb_insert(root->link[dir],data);
update(root);
if(is_red(root->link[dir])){
if(is_red(root->link[!dir])){
root->red = 1;
root->link[0]->red = root->link[1]->red = 0;
}
else{
if(is_red(root->link[dir]->link[dir]))root = rotate1(root,!dir);
else if(is_red(root->link[dir]->link[!dir]))root = rotate2(root,!dir);
}
}
}
return root;
}
int count_(int k,node *root){
if(!root)return 0;
int dir = root->data <= k;
if(dir)return get_size(root->link[0]) + 1 + count_(k,root->link[1]);
else return count_(k,root->link[0]);
}
void remove_memory(node* &root)
{
if(!root)return;
remove_memory(root->link[0]);
remove_memory(root->link[1]);
free(root);
}
int min_ele(node *root)
{
if(!root->link[0])return root->data;
return min_ele(root->link[0]);
}
void dfs(int x,int fa)
{
down[x] = 1;
for(int i=st[x];i;i=nxt[i]){
if(en[i] == fa || cut[en[i]])continue;
dfs(en[i], x);
down[x] += down[en[i]];
}
}
int find_mid(int x)
{
int mid = down[x]/2, i;
for(;;){
for(i=st[x];i;i=nxt[i]){
if(cut[en[i]] || down[en[i]] > down[x])continue;
if(down[en[i]] > mid){x = en[i];break;}
}
if(!i)break;
}
return x;
}
void Insert_dfs(int x,int fa,int L)
{
if(is[x])Root = rb_insert(Root, L);
for(int i=st[x];i;i=nxt[i]){
if(en[i] == fa || cut[en[i]])continue;
Insert_dfs(en[i], x, L + len[i]);
}
}
ll Find_dfs(int x,int fa,int L,int k)
{
ll res = 0;
if(is[x]){
res += count_(k - L, Root);
if(Root)MIN = min(MIN, L + min_ele(Root));
}
for(int i=st[x];i;i=nxt[i]){
if(en[i] == fa || cut[en[i]])continue;
res += Find_dfs(en[i], x, L + len[i], k);
}
return res;
}
ll solve(int x,int k)
{
dfs(x, -1);
if(down[x] <= 1)return 0;
int fi = find_mid(x);
ll res = 0;
cut[fi] = 1;
if(is[fi])Root = rb_insert(Root, 0);
for(int i=st[fi];i;i=nxt[i]){
if(cut[en[i]])continue;
res += Find_dfs(en[i],-1,len[i],k);
Insert_dfs(en[i],-1,len[i]);
}
remove_memory(Root); Root = 0;
for(int i=st[fi];i;i=nxt[i]){
if(cut[en[i]])continue;
res += solve(en[i], k);
}
return res;
}
ll lower(int x)
{
memset(cut, 0, sizeof cut);
return solve(1, x);
}
int flag = 0;
int q1[N_], q2[N_];
int LL[N_];
int top1, top2;
ll lower2(int x, int L, int H)
{
if(L == H)return 0;
int m = (L+H)>>1;
int i, cnt = 0;
top1 = top2 = 0;
for(i=m;i>=L;i--){
if(is[i])q1[top1++] = cnt;
cnt += LL[i];
}
cnt = 0;
for(i=m+1;i<=H;i++){
cnt += LL[i];
if(is[i])q2[top2++] = cnt;
}
int j = 0;
ll ans = 0;
for(i=0;i<top1;i++){
while(j != top2 && q2[j] + q1[i] <= x)++j;
ans += j;
}
return ans + lower2(x, L, m) + lower2(x, m+1, H);
}
int main()
{
scanf("%d%d%lld",&n,&m,&K);
int i;
for(i=2;i<=n;i++){
int x, y;
scanf("%d%d",&x,&y);
LL[i] = y;
addE(i, x, y, i<<1);
addE(x, i, y, i<<1|1);
if(x != i-1)flag = 1;
}
for(i=1;i<=m;i++){
int x;
scanf("%d",&x);
is[x] = 1;
}
int low = 1, high = 250 * 100000 + 5, mid, ans;
while(low <= high){
mid = (low + high) >> 1;
if(!flag){
if(lower(mid) >= K)ans = mid, high = mid - 1;
else low = mid + 1;
if(K == 1){
printf("%d",MIN);
return 0;
}
}
else{
if(lower2(mid, 1, n) >= K)ans = mid, high = mid - 1;
else low = mid + 1;
}
}
printf("%d",ans);
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
6288 KB |
Output is correct |
| 2 |
Correct |
0 ms |
6288 KB |
Output is correct |
| 3 |
Correct |
0 ms |
6288 KB |
Output is correct |
| 4 |
Correct |
0 ms |
6288 KB |
Output is correct |
| 5 |
Correct |
0 ms |
6288 KB |
Output is correct |
| 6 |
Correct |
0 ms |
6288 KB |
Output is correct |
| 7 |
Correct |
0 ms |
6288 KB |
Output is correct |
| 8 |
Correct |
0 ms |
6288 KB |
Output is correct |
| 9 |
Correct |
0 ms |
6288 KB |
Output is correct |
| 10 |
Correct |
0 ms |
6288 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
36 ms |
6288 KB |
Output is correct |
| 2 |
Correct |
100 ms |
6392 KB |
Output is correct |
| 3 |
Correct |
88 ms |
6540 KB |
Output is correct |
| 4 |
Correct |
432 ms |
7076 KB |
Output is correct |
| 5 |
Correct |
1588 ms |
8844 KB |
Output is correct |
| 6 |
Execution timed out |
6000 ms |
12260 KB |
Program timed out |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
6288 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
6288 KB |
Output is correct |
| 2 |
Incorrect |
8 ms |
6288 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
6288 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
