제출 #238619

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
238619		Ruxandra985	경주 (Race) (IOI11_race)	C++14	100 / 100	460 ms	93176 KiB

race

#include <bits/stdc++.h>
#include "race.h"
#define DIMN 200010
#define MAX_N 500000
using namespace std;
 
vector < pair <int,int> > v[DIMN];
set < pair <long long,int> > per[DIMN];
int sub[DIMN] , f[DIMN] , distanta[DIMN];
long long add[DIMN];
int sol;
 
void precalc (int nod , int tt){
    int i , vecin;
 
    sub[nod] = 1;
    for (i = 0 ; i < v[nod].size() ; i++){
        vecin = v[nod][i].first;
        if (vecin != tt && !f[vecin]){
            precalc (vecin , nod);
            sub[nod] += sub[vecin];
        }
    }
 
}
 
void dfs (int nod , int tt , int k){
    int i , vecin , maxi = 0 , fiu ;
    long long rms;
    set < pair <long long,int> > :: iterator aux;
 
    for (i = 0 ; i < v[nod].size() ; i++){
        vecin = v[nod][i].first;
        if (vecin != tt && sub[vecin] > maxi){
            maxi = sub[vecin];
            fiu = vecin;
        }
    }
 
 
    for (i = 0 ; i < v[nod].size() ; i++){
        vecin = v[nod][i].first;
        if (vecin != tt){
            dfs (vecin , nod , k);
            add[vecin] += v[nod][i].second;
            distanta[vecin]++;
        }
    }
 
 
    if (maxi){
 
        per[nod].swap(per[fiu]);
        add[nod] = add[fiu];
        distanta[nod] = distanta[fiu];
 
        for (i = 0 ; i < v[nod].size() ; i++){
            vecin = v[nod][i].first;
 
            if (vecin != tt){
 
                if (vecin != fiu){
                    rms = k - v[nod][i].second - add[nod];
 
                    aux = per[nod].upper_bound(make_pair(rms , -2000000000));
 
                    if (aux != per[nod].end() && aux->first == rms){
 
                        sol = min(sol , 1 + aux->second + distanta[nod]);
 
                    }
                }
 
 
                per[nod].insert(make_pair(v[nod][i].second - add[nod] , 1 - distanta[nod]));
 
 
            }
 
            if (vecin != tt && vecin != fiu){
 
                /// sa zicem ca nod ar fi lca - ul , un capat pana acum , unul in vecin
 
                for (set <pair <long long,int> > :: iterator it = per[vecin].begin() ; it != per[vecin].end() ; it++){
 
                    if (it->first + add[vecin] > k)
                        continue;
 
                    rms = k - (it->first + add[vecin]) - add[nod];
 
                    aux = per[nod].upper_bound(make_pair(rms , -2000000000));
 
                    if (aux != per[nod].end() && aux->first == rms){
 
                        sol = min(sol , it->second + distanta[vecin] + aux->second + distanta[nod]);
 
                    }
 
                }
 
 
 
                /// vezi cum le unesti
 
                for (set <pair <long long,int> > :: iterator it = per[vecin].begin() ; it != per[vecin].end() ; it++){
 
                    if (it->first + add[vecin] > k)
                        continue; /// nu imi pasa
 
 
                    per[nod].insert(make_pair(it->first + add[vecin] - add[nod] , it->second + distanta[vecin] - distanta[nod]));
 
 
                }
 
 
            }
        }
 
 
    }
 
    aux = per[nod].upper_bound(make_pair(k - add[nod] , -2000000000));
    if (aux != per[nod].end() && aux->first == k - add[nod]){
        sol = min(sol , aux->second + distanta[nod]);
    }
 
}
 
int best_path(int n, int k, int h[][2], int l[]){
    int i;
 
    for (i = 0 ; i < n - 1 ; i++){
 
        h[i][1]++;
        h[i][0]++;
 
        v[h[i][0]].push_back(make_pair(h[i][1] , l[i]));
        v[h[i][1]].push_back(make_pair(h[i][0] , l[i]));
 
    }
 
    precalc (1 , 0);
 
    sol = 2000000000;
 
    dfs (1 , 0 , k);
 
    return (sol == 2000000000 ? -1 : sol);
 
}

컴파일 시 표준 에러 (stderr) 메시지

race.cpp: In function 'void precalc(int, int)':
race.cpp:17:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 0 ; i < v[nod].size() ; i++){
                  ~~^~~~~~~~~~~~~~~
race.cpp: In function 'void dfs(int, int, int)':
race.cpp:32:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 0 ; i < v[nod].size() ; i++){
                  ~~^~~~~~~~~~~~~~~
race.cpp:41:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 0 ; i < v[nod].size() ; i++){
                  ~~^~~~~~~~~~~~~~~
race.cpp:57:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (i = 0 ; i < v[nod].size() ; i++){
                      ~~^~~~~~~~~~~~~~~
race.cpp:28:32: warning: 'fiu' may be used uninitialized in this function [-Wmaybe-uninitialized]
     int i , vecin , maxi = 0 , fiu ;
                                ^~~

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