Submission #29254

#	Time	Username	Problem	Language	Result	Execution time	Memory
29254		ozaslan	Race (IOI11_race)	C++14	100 / 100	1363 ms	45144 KiB

race

#include<bits/stdc++.h>
#include "race.h"
#define MAX_N 500000
#define oo (1<<28)
#define pb push_back
#define mp make_pair
#define ff first
#define ss second

using namespace std;

/*static int N, K;
static int H[MAX_N][2];
static int L[MAX_N];
static int solution;

inline
void my_assert(int e) {if (!e) abort();}

void read_input()
{
  int i;
  my_assert(2==scanf("%d %d",&N,&K));
  for(i=0; i<N-1; i++)
    my_assert(3==scanf("%d %d %d",&H[i][0],&H[i][1],&L[i]));
  my_assert(1==scanf("%d",&solution));
}

int main()
{
    freopen("grader.in.3", "r", stdin);
  int ans;
  read_input();
  ans = best_path(N,K,H,L);
  if(ans==solution)
    printf("Correct.\n");
  else
    printf("Incorrect. Returned %d, Expected %d.\n",ans,solution);

  return 0;
}*/

int enIyi = oo;
int kul[MAX_N], cocukSayisi[MAX_N], hedef;
map<int, int> uzak;
vector< pair<int, int> > E[MAX_N];
int uzaklik[MAX_N], derin[MAX_N];

int merkezDFS(int dugum, int ata) {
   cocukSayisi[dugum] = 0;

	int s = E[dugum].size();
	for (int i = 0; i < s; i++) {
		int v = E[dugum][i].first;

		if(v != ata && !kul[v])
			cocukSayisi[dugum] += merkezDFS(v, dugum);
	}
   return cocukSayisi[dugum] +1;
}

int merkezBul(int bas) {
	int uyeSayisi = merkezDFS(bas, -1);
    if (uyeSayisi == 1) return -1;

    int ata = -1;
    int dugum = bas;
 	while (1) {
 		bool bayrak = 1;

		int s = E[dugum].size();
		for (int i = 0; i < s; i++) {
            int v = E[dugum][i].first;
            int cocuk = cocukSayisi[v]+1;

            if(kul[v]) continue;
            if (v == ata) cocuk -= (cocukSayisi[dugum]+1);

			if (cocuk > uyeSayisi/2) {
				bayrak = 0;
				ata = dugum;
				dugum = v;
				break;
            }
		}
		if (bayrak) return dugum;
  }

}

int DFS(int dugum, int mesafe, int derinlik, int ata, int sayac) {
   // printf("Dugum: %d\n", dugum);
    if (uzak.find(hedef-mesafe) != uzak.end()) {
        enIyi = min(enIyi, derinlik + uzak[hedef-mesafe]);
     //   printf("derinlik: %d, mesafe:%d, dugum:%d\n", derinlik, mesafe, dugum);
    }
    uzaklik[sayac] = mesafe;
    derin[sayac] = derinlik;

    int s = E[dugum].size();
    for (int i = 0; i < s; i++) {
        int v = E[dugum][i].first, m = E[dugum][i].second;
        if (v == ata || kul[v]) continue;

        sayac = DFS(v, mesafe +m, derinlik+1, dugum, sayac+1);
    }

    return sayac;
}

void centeroid(int bas) {
    uzak.clear();
    uzak[0] = 0;

	int merkez = merkezBul(bas);
    if(merkez == -1) {kul[bas] = 1; return;}

//    printf("Merkez: %d \n", merkez);

    int s = E[merkez].size();
    for (int i = 0; i < s; i++) {
        int v = E[merkez][i].first, m = E[merkez][i].second;
  //      printf("M: %d, v: %d", merkez, v);
        if(kul[v]) continue;
        int sayac = DFS(v, m, 1, merkez, 0);

    //    printf("\n");
        for(int j=0; j<=sayac; j++) {
            if(uzak.find(uzaklik[j]) == uzak.end()) uzak[uzaklik[j]] = derin[j];
            else uzak[uzaklik[j]] = min(uzak[uzaklik[j]], derin[j]);
        }
    }
  //  printf("Kontrol\n");
    kul[merkez] = 1;

    for (int i = 0; i < s; i++)
        if(!kul[E[merkez][i].first])
            centeroid(E[merkez][i].first);

}

int best_path(int N, int K, int H[][2], int L[])
{
    hedef = K;

	for (int i = 0; i < N-1; i++) {
    //    cout << H[i][0] << " " << H[i][1] << endl;
		E[ H[i][0] ].push_back( make_pair( H[i][1], L[i]) );
		E[ H[i][1] ].push_back( make_pair( H[i][0], L[i]) );
	}

	centeroid(0);

    if(enIyi == oo) enIyi = -1;
	return enIyi;
}

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