t0nyukuk's blog

how can i solve this problem ?
By t0nyukuk, 12 years ago, In English

http://orac.amt.edu.au/fario/11/problems_en.pdf fourth problem

  • Vote: I like it
  • +3
  • Vote: I do not like it

»
12 years ago, # |
← Rev. 2   Vote: I like it +4 Vote: I do not like it

It looks like a usual dp on a tree. I think you should write a comparator, like 'What vertex we should go into?'. Then run DFS, and at each step sort all children of the current vertex by this comparator and visit them in this exact order. Once you visit a subtree, it becomes a vertex with its own parameters.

I may be wrong, but it's the first solution I would think of.

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    i will write comparator but which priority? i have no idea

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
      ← Rev. 3   Vote: I like it +3 Vote: I do not like it

      Write the mathematical expression, what number of citizen will be dead if we go to the first city and then to the second. Then write the same expression if you visit the cities in the opposite order. Sign of the difference of these values will show which city of these two should be visited first.

      → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        i try this but i can't, i will try this once again

        → Reply
»
12 years ago, # |
← Rev. 7   Vote: I like it +2 Vote: I do not like it

my code is here and i dont know is it true solution

define fi first

define se second

define SIZE(A) ((int)A.size())

define pb push_back

using namespace std;

const int MAXN = 100010;

typedef pair<int,int> ii;

vector way[MAXN];

int n;

long long vic[MAXN];

struct node{

long long a,b,w,len;

node(int _a=0,int _b=0,int _w=0,int _len=0){

    a=_a;b=_b;w=_w;len=_len;

}

friend bool operator < (const node &a,const node &b){

    return a.b*b.a<b.b*a.a;

}

}ar[MAXN];

typedef set::iterator sit;

set G[MAXN];

bool used[MAXN];

node rec(int k,int t){

used[k]=true;
ar[k].w=k;
ar[k].len=t;
ar[k].b=t*2;
ar[k].a=vic[k];
node tmp;
for(int i=0;i<SIZE(way[k]);i++)
    if(!used[way[k][i].fi]){
       tmp=rec(way[k][i].fi,way[k][i].se);
       G[k].insert(tmp);
       ar[k].b+=tmp.b;
       ar[k].a+=tmp.a;
    }
return ar[k];

}

long long f(int k){

used[k]=true;
long long res=0;
long long time=0;

for(sit it=G[k].begin();it!=G[k].end();it++)
    if(!used[it->w]){

       res+=time*it->a+f(it->w)+it->len*it->a;

       time+=it->b;

    }

return res;

}

int main(){

scanf(" %d",&n);

for(int i=1;i<=n;i++)
    scanf(" %lld",&vic[i]);

for(int i=1,a,b,c;i<n;i++)
{
    scanf("%d %d %d",&a,&b,&c);
    way[a].pb(ii(b,c));
    way[b].pb(ii(a,c));
}
rec(1,0);
memset(used,0,sizeof used);

cout << f(1) << endl;

return 0;

}

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    my bug is "set", it will be "multiset". thanks dalex

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Use vectors + sorting next time, it should be a bit faster than sets with their red-black trees.

      → Reply
»
12 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

AppleZ the previous comment for my wrong idea. Thanks

→ Reply