Submission #1087806

#	Time	Username	Problem	Language	Result	Execution time	Memory
1087806		nmts	Race (IOI11_race)	C++17	100 / 100	320 ms	50516 KiB

race

#include <bits/stdc++.h>

#define file(name) freopen(name".inp" , " r " , stdin);freopen(name".out" , " w " , stdout);
#define faster    ios_base :: sync_with_stdio(false) ; cin.tie(0) ; cout.tie(0) ;
#define pii pair < int , int >
#define fi first
#define se second
#define mii map< int , int>
#define reset(a,val) memset(a ,val , sizeof(a) )
#define endl '\n'    
#define ll long long
const int maxn = 1e6 + 6;
const int mod= 1e9 + 7;
const ll INFLL= 3e18 + 5;
const int INF = 1e9 + 5 ;
const int LOG = 20 ;


template <class T> inline T sqr(T x) { return x * x; };

template <class T> inline int Power(T x, int y) 

{ if (!y) return 1; if (y & 1) return sqr(Power(x, y / 2)) % mod * x % mod; return sqr(Power(x, y / 2)) % mod; }

template<class T> bool minimize(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool maximize(T& a, const T& b) { return a < b ? a = b, 1 : 0; }

inline int gcd(int x, int y) 
{ return y ? gcd(y , x % y) : x;}

inline int lcm(int x, int y) { return x * y / gcd(x, y); }

using namespace std;

int n;
ll ans = INF;
vector<pii> edges[maxn];
int k;
ll cnt[maxn];

struct CD{

    int sz[maxn];
    bool del[maxn];

    int dfs(int u , int p)
        {

            sz[u] = 1;

            for (auto&[v  , w] : edges[u])
                if (v != p && del[v] == 0)
                    sz[u] += dfs(v , u);

            return sz[u];

        }

    int find_centroid(int u , int p  , int total)
        {

            for (auto&[v , w] : edges[u])
                if (v != p && del[v] == 0 && sz[v] > total / 2)
                    return find_centroid(v ,u , total);

            return u;

        }

    void calc(int u , int p, int l , int h ,  int t)
        {
            if (l > k) return;
            if (t == 0) 
                {
                    minimize(ans , cnt[k - l] + h);
                    // cout << l << " " << cnt[k - l] + h << endl;
                }
            else if (t == 1) cnt[l] = min(cnt[l] , 1ll *h);
            else cnt[l] = INF + INF;

            for (auto&[v , w]: edges[u])
                if (v != p && del[v] == 0)
                    calc(v , u , l + w , h + 1 , t);

        }

    void decompose(int u )
        {

            u = find_centroid(u , 0 , dfs(u , 0));

            del[u] = 1;
            // cerr << u << endl;
            for (auto&[v , w] : edges[u])
                if (del[v] == 0)
                    {
                        calc(v , u , w , 1 , 0);
                        calc(v , u , w , 1 , 1);
                    }       

            for (auto&[v ,w] : edges[u])
                if (del[v] == 0)
                    calc(v , u , w , 1  , -1);

            for (auto&[v , w]: edges[u] )
                if (del[v] == 0)
                    {
                        decompose(v);
                    }
           

        }

} cd;

// void solve()
// {

//     cin >> n >> k;

//     for (int i = 1 ; i < n ; ++i)
//         {
//             int u , v , w; cin >> u >> v >> w;
//             ++u , ++v;
//             edges[u].push_back({v , w});
//             edges[v].push_back({u , w});
//         }
//     memset(cnt , INF + INF , sizeof cnt);
//     cnt[0] = 0;
//     cd.decompose(1);

//     cout << (ans >= INF ? -1 : ans) << endl;

// }
int best_path(int _n, int _k, int H[][2], int l[]) 
{
	n = _n;
	k = _k;
	memset(cnt , INF + INF , sizeof cnt);
	cnt[0] = 0;
	for (int i = 0; i < n - 1; i++)
	{
	  int w = l[i];
	  int u = H[i][0] + 1, v = H[i][1] + 1;
	  edges[u].push_back({v, w});
	  edges[v].push_back({u, w});
	}
	
	cd.decompose(1);
	
	return (ans >= INF ? -1 : ans);
}


// int32_t main()
// {
//     faster;
//     // file("txt");
//     // int t ; cin >> t ; while (t--)
//     solve();
//     return 0;
// } 

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