Submission #246925

#	Time	Username	Problem	Language	Result	Execution time	Memory
246925		DavidDamian	Traffic (IOI10_traffic)	C++11	100 / 100	1423 ms	138872 KiB

traffic

#include <bits/stdc++.h>
using namespace std;
///Tree rotations
///Determine the node with minimum congestion (maximum subtree size)
vector<int> adjList[1000006];
int subtreeSize[1000006];
int value[1000006];
void computeSubtree(int u,int p)
{
    subtreeSize[u]=value[u];
    for(int v: adjList[u]){
        if(v==p) continue;
        computeSubtree(v,u);
        subtreeSize[u]+=subtreeSize[v];
    }
}
int minimum=INT_MAX;
int centre=-1;
void Rotate(int u,int p)
{
    int maxChild=0;
    for(int v: adjList[u]){
        maxChild=max(maxChild,subtreeSize[v]);
    }
    if(maxChild<minimum){
        minimum=maxChild;
        centre=u;
    }
    for(int v: adjList[u]){
        if(v==p) continue;
        subtreeSize[u]-=subtreeSize[v];
        subtreeSize[v]+=subtreeSize[u];
        Rotate(v,u);
        subtreeSize[v]-=subtreeSize[u];
        subtreeSize[u]+=subtreeSize[v];
    }
}
int LocateCentre(int n,int P[],int S[],int D[])
{
    for(int i=0;i<n-1;i++){
        adjList[ S[i] ].push_back(D[i]);
        adjList[ D[i] ].push_back(S[i]);
        value[i]=P[i];
    }
    value[n-1]=P[n-1];
    computeSubtree(0,-1);
    Rotate(0,-1);
    return centre;
}

• Subtask 1: 25 / 25
• Subtask 2: 25 / 25
• Subtask 3: 25 / 25
• Subtask 4: 25 / 25