Saratov State University :: Online Contester


::Go
- home
- news
- register
- update personal info
- problemset archive
- submit
- status online
- standing
- contests
- virtual contests
- forum
- statistic
- FAQ
- links
- projects

::Poll
Are you registered on Codeforces?
Yes
No
What is it???

[results]

::webboard

WA on test 63
Author: keepcalmandsolve
ID: 055503
Problem: 534
Contest: 0
Date: 2014-12-31 21:26:39

I don't know where is my bug? Can anyone help?
Thanks in advance.



//In the name of ALLAH

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cassert>
#include <stack>

using namespace std;

#define err(x) cout<<#x<<" : "<<x<<'n';;
typedef pair<int,int> pii;
typedef long long ll;
const ll N=100000+100;
const ll M=100000+100;
const ll INF=20000*1000*100;

//lp[0][i] = logest path in subtree 'i'
//lp[1][i] = second logest path in subtree 'i'
//t[e],p[e] = value for edge 'e'
//dep[i] = depth of vertex 'i'
//pe[i] = index of edge from 'i' to 'dad[i]'
//cntlp[i] = number of longest paths in subtree 'i'
//eans[i] = 'true':means the edge to its dad(dad[i]) must be removed, 'false':otherwise

int n;
ll t[M],p[M],lp[2][N],dep[N],pe[N],dad[N],cntlp[N];
vector<pii> adj[N];
ll ans[N];
bool eans[N];
stack <int> rmv;

void dfs(int v,int par=-1){
dad[v]=par;
lp[0][v]=lp[1][v]=cntlp[v]=0;
for (int u,i=0;i<(int)adj[v].size();i++)
if (adj[v][i].first!=par){
dep[u = adj[v][i].first]=dep[v]+1;
pe[u] = adj[v][i].second;
dfs(u,v);
if (lp[0][v] < lp[0][u] + t[pe[u]]) lp[0][v] = lp[0][u] + t[pe[u]];
}

for (int u,i=0;i<(int)adj[v].size();i++)
if (lp[1][v] < lp[0][u=adj[v][i].first] + t[pe[u]]){
if (lp[0][u] + t[pe[u]] < lp[0][v]) lp[1][v] = lp[0][u] + t[pe[u]];
else cntlp[v]++;
}
}


void solve (int v,int par){
ll sum=0;
bool isleaf=true;
for (int i=0;i<(int)adj[v].size();i++)
if (adj[v][i].first!=par){
isleaf=false;
solve(adj[v][i].first, v);
}
for (int u,i=0;i<(int)adj[v].size();i++)
if (adj[v][i].first!=par && lp[0][u=adj[v][i].first] + t[adj[v][i].second] == lp[0][v])
sum += ans[u];

if (isleaf || p[pe[v]] < sum){
ans[v] = p[pe[v]];
eans[v] = true;
}
else{
ans[v]=sum;
eans[v] = false;
}
}

// finds for vertex 'v' the list of edge that must be deleted to reduce the diameter
void remove(int v){
if (eans[v]){
rmv.push(pe[v]); return;
}
for (int u,i=0;i<(int)adj[v].size();i++)
if (adj[v][i].first!=dad[v] && lp[0][u=adj[v][i].first] + t[adj[v][i].second] == lp[0][v])
remove(u);
}


int main(){
scanf("%d",&n);
for (int a,b,i=1;i<n;i++){
scanf("%d%d%I64d%I64d",&a,&b,t+i,p+i);
adj[a].push_back(pii(b,i)); adj[b].push_back(pii(a,i));
}

dep[0]=dep[1]=0;
dfs(1);
ll diam=0; int root=0;
for (int i=1;i<=n;i++){
if (cntlp[i]==1 && lp[0][i]+lp[1][i] > diam) diam = lp[0][i] + lp[1][i];
else if (cntlp[i]>1 && lp[0][i] * 2 > diam) diam = 2*lp[0][i];
}
for (int i=1;i<=n;i++){
if (cntlp[i]==1 && lp[0][i]+lp[1][i] == diam && dep[i]>=dep[root]) root=i;
else if (cntlp[i]>1 && lp[0][i]*2 == diam) root=i;
}

// now we have found the vertex 'root' which is in all of diametres
dfs(root); // --> updating values of lp[],... in the new tree rooted at vertex 'root'
for (int i=0;i<(int)adj[root].size();i++){
pe[adj[root][i].first] = adj[root][i].second;
solve(adj[root][i].first, root); // finds for each vertex 'i': the minimum cost we should pay to reduce longest path from subtree 'i'
}

int nlp[2]={0,0}; // nlp[0] = number of longest paths nlp[1] = number of second longest paths
for (int u,i=0;i<(int)adj[root].size();i++){
if (lp[0][u=adj[root][i].first] + t[pe[u]] == lp[0][root]) nlp[0]++ ;
if (lp[0][u] + t[pe[u]] == lp[1][root]) nlp[1]++;
}

ll res=0,maxi=-1;
if (nlp[0]>1){
for (int u,i=0;i<(int)adj[root].size();i++)
if (lp[0][u=adj[root][i].first] + t[pe[u]] == lp[0][root]){
res += ans[u];
maxi=max(maxi, ans[u]);
}
bool found=false;
for (int u,i=0;i<(int)adj[root].size();i++){
if (lp[0][u=adj[root][i].first] + t[pe[u]] == lp[0][root] && ans[u]==maxi && !found) found=true;
else if (lp[0][u=adj[root][i].first] + t[pe[u]] == lp[0][root]) remove(u);
}

assert(maxi>0);
printf("%dn",res-maxi);
printf("%dn",(int)rmv.size());
int z;
while (!rmv.empty()){
z = rmv.top(); rmv.pop();
printf("%d ",z);
}
printf("n");
}
else {
assert(nlp[0]==1);

ll res2=0;
for (int i=0;i<(int)adj[root].size();i++)
if (lp[0][adj[root][i].first] + t[pe[adj[root][i].first]] == lp[0][root]){
res2 = ans[adj[root][i].first];
remove(adj[root][i].first) ; break;
}

for (int u,i=0;i<(int)adj[root].size();i++)
if (lp[0][u=adj[root][i].first] + t[pe[u]] == lp[1][root])
res += ans[u];

if (nlp[1]==0) res=INF;
printf("%dn",min(res,res2)); // min(res,res2) : we must destroy (all of second longest paths) OR (the longest path)

if (res<res2){
rmv.pop();
for (int u,i=0;i<(int)adj[root].size();i++)
if (lp[0][u=adj[root][i].first] + t[pe[u]] == lp[1][root])
remove(u);
}

printf("%dn",(int)rmv.size());
int z;
while (!rmv.empty()){
z = rmv.top(); rmv.pop();
printf("%d ",z);
}
printf("n");
}

return 0;
}

see sub-tree reply to that message


::Login
Forgot password?

::News
22.10.12 - The problems from the Southern Subregional Programming Contest 2012 added to the problemset archive (542 - 553).
22.10.12 - After the start of the contest the statements in PDF will be available by the link.
23.10.11 - The problems from the Southern Subregional Programming Contest 2011 added to the problemset archive (530 - 541).

::Counter

Server time: 2017-09-22 21:10:24Online Contester Team © 2002 - 2016. All rights reserved.