Submission #760328

#	Time	Username	Problem	Language	Result	Execution time	Memory
760328		Andrei_Calota	Race (IOI11_race)	C++14	0 / 100	5 ms	9756 KiB

race

#include "race.h"
#include <bits/stdc++.h>


using namespace std;
using int64 = long long;

const int N_MAX = 2e5;
const int K_MAX = 1e6;



struct defEdge {
   int from, to, cost;
}; vector<defEdge> tree[1 + N_MAX];
int n, k; int sizOf[1 + N_MAX];
int64 preffSum[1 + N_MAX]; int depth[1 + N_MAX];

void auxDFS (int root, int p, int cost)  {
    preffSum[root] = preffSum[p] + cost;
    depth[root] = depth[p] + 1;

    for (defEdge e : tree[root])
       if (e.to != p)
         auxDFS (e.to, root, e.cost);
    sizOf[root] = 1;
    for (defEdge e : tree[root])
       sizOf[root] += sizOf[e.to];
}

const int NONE = -1;

map<int64, int> minDist; /// minDist[k] = numarul minim de muchii cu distanta k
vector<int> subTree[1 + N_MAX];
int answer[1 + N_MAX]; /// answer[root] = numarul minim de muchii care trec prin root cu suma k

void DFS (int root, int p, bool toEliminate) {
    int maxSize = 0, heavyChild = NONE;
    for (defEdge e : tree[root])
       if (e.to != p && sizOf[e.to] > maxSize)
         maxSize = sizOf[e.to], heavyChild = e.to;

    for (defEdge e : tree[root])
       if (e.to != p && e.to != heavyChild)
         DFS (e.to, root, true);

    if (heavyChild != NONE) {
      DFS (heavyChild, root, false);
      swap (subTree[root], subTree[heavyChild]);
    }

    int64 target = k + 2 * preffSum[root];

    subTree[root].push_back (root);
    minDist[preffSum[root]] = depth[root];

    if (target > preffSum[root] && minDist[target - preffSum[root]])
      answer[root] = minDist[target - preffSum[root]] - minDist[preffSum[root]];

    for (defEdge e : tree[root]) {
       if (e.to != p && e.to != heavyChild) {
         for (int aux : subTree[e.to])
            if (target > preffSum[aux] && minDist[target - preffSum[aux]])
              answer[root] = min (answer[root], minDist[target - preffSum[aux]] + depth[aux] - 2 * depth[root]);
         for (int aux : subTree[e.to]) {
            subTree[root].push_back (aux);
            if (!minDist[preffSum[aux]] || minDist[preffSum[aux]] > depth[aux])
              minDist[preffSum[aux]] = depth[aux];
         }
       }
    }

    if (toEliminate)
      for (int aux : subTree[root])
         minDist[preffSum[aux]] = 0;
}

const int PAIR = 2;
int best_path (int N, int K, int H[][PAIR], int L[]) {
   n = N, k = K;
   for (int i = 0; i < N - 1; i ++) {
      int u = H[i][0], v = H[i][1]; u ++, v ++;
      tree[u].push_back ({u, v, L[i]});
      tree[v].push_back ({v, u, L[i]});
   }
   depth[0] = NONE, preffSum[0] = 0;
   auxDFS (1, 0, 0); DFS (1, 0, true);

   for (int node = 1; node <= n; node ++)
      answer[node] = 1 + N_MAX;
   int miny = answer[1];
   for (int node = 2; node <= n; node ++)
      miny = min (miny, answer[node]);

   if (miny == 1 + N_MAX)
     return NONE;
   return miny;
}

/**void TestOut (void) {
    cin >> n >> k;
    for (int i = 1; i < n; i ++) {
       int u, v, cost; cin >> u >> v >> cost; u ++, v ++;
       tree[u].push_back ({u, v, cost});
       tree[v].push_back ({v, u, cost});
    }
    depth[0] = NONE, preffSum[0] = 0; auxDFS (1, 0, 0);
    for (int node = 1; node <= n; node ++)
       cout << depth[node] << " " << preffSum[node] << "\n";

    for (int node = 1; node <= n; node ++)
       answer[node] = 1 + N_MAX;
    DFS (1, 0, true);

    for (int node = 1; node <= n; node ++)
       cout << answer[node] << " ";
}**/

/**int main()
{
   ///TestOut ();
    return 0;
}**/

• Subtask 1: 0 / 9
• Subtask 2: 0 / 12
• Subtask 3: 0 / 22
• Subtask 4: 0 / 57