oj.uz

답안 #1068444

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1068444 2024-08-21T09:54:37 Z apper 경주 (Race) (IOI11_race) C++17
21 / 100
 193 ms 63416 KB 
#include "race.h"

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define ll long long 
#define pb push_back
using namespace std;
using namespace __gnu_pbds;
/*------------------------------------code------------------------------------*/
const ll MAXN=1e5+9;
const ll INF=1e9+9;
const ll R=(1<<18);
const int X=18;
//const ll M=1e9+7;
//const ll P=47;

int n, k;
vector<pair<int, int>> adj[MAXN];
vector<int> sz(MAXN);
vector<int> done(MAXN);
int ans=INF, curr;
vector<int> dist[1000009];
vector<int> deg(MAXN);
vector<int> group(MAXN);

int dfs(int v, int p)
{
	sz[v]=1;
	for(auto [u, w] : adj[v])
	{
		if(u==p || done[u])
			continue;
		sz[v]+=dfs(u, v);
	}
	return sz[v];
}

int get(int v, int p, int mx)
{
	for(auto [u, w] : adj[v])
	{
		if(u==p || done[u])
			continue;
		if(sz[u]>mx)
			return get(u, v, mx);
	}
	return v;
}

void mark(int v, int p, ll d)
{
	dist[d].pb(v);
	group[v]=curr;
	deg[v]=deg[p]+1;
	for(auto [u, w] : adj[v])
	{
		if(u==p || done[u] || d+w>k || deg[v]>=ans)
			continue;
		mark(u, v, d+w);
	}
}

void solve(int v, int p, ll d)
{
	if(d==k)
	{
		ans=min(ans, deg[v]);
		return;
	}
	for(int u : dist[k-d])
		if(group[u]!=group[v])
			ans=min(ans, deg[v]+deg[u]);
	for(auto [u, w] : adj[v])
	{
		if(u==p || done[u] || d+w>k || deg[v]>=ans)
			continue;
		solve(u, v, d+w);
	}
}

void cls(int v, int p, ll d)
{
	group[v]=deg[v]=0;
	dist[d].pop_back();
	for(auto [u, w] : adj[v])
		if(group[u])
			cls(u, v, d+w);
}

void decompose(int v)
{
	int c = get(v, -1, dfs(v, -1)/2);
	done[c]=true;
	deg[c]=0;
	curr=1;
	for(auto [u, w] : adj[c])
	{
		if(done[u] || w>k)
			continue;
		mark(u, c, w);
		curr++;
	}
	for(auto [u, w] : adj[c])
	{
		if(done[u] || w>k)
			continue;
		solve(u, c, w);
	}
	
	
		
		
	for(auto [u, w] : adj[c])
		if(!done[u] && w<=k)
			cls(u, v, w);
	for(auto [u, w] : adj[c])
		if(!done[u])	
			decompose(u);
}

int best_path(int N, int K, int edges[][2], int weights[]) 
{
	if(k==1) 
		return 0;
	n=N;
	k=K;
	for(int i=0;i<n-1;i++)
	{
		int u = edges[i][0];
		int v = edges[i][1];
		adj[u].pb({v, weights[i]});
		adj[v].pb({u, weights[i]});
	}
	decompose(1);
	return (ans==INF ? -1 : ans);
}

/*
int main()
{
    cin.tie(0); ios_base::sync_with_stdio(0);
	solve();
	return 0;
}
*/

Subtask #1
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 27660 KB Output is correct
2 Correct 16 ms 27740 KB Output is correct
3 Correct 12 ms 27740 KB Output is correct
4 Correct 12 ms 27668 KB Output is correct
5 Correct 15 ms 27736 KB Output is correct
6 Correct 12 ms 27872 KB Output is correct
7 Correct 13 ms 27696 KB Output is correct
8 Correct 15 ms 27740 KB Output is correct
9 Correct 17 ms 27996 KB Output is correct
10 Correct 14 ms 27744 KB Output is correct
11 Correct 12 ms 27736 KB Output is correct
12 Correct 15 ms 27812 KB Output is correct
13 Correct 18 ms 27792 KB Output is correct
14 Correct 12 ms 27736 KB Output is correct
15 Correct 13 ms 27672 KB Output is correct
16 Correct 10 ms 27740 KB Output is correct
17 Correct 17 ms 27740 KB Output is correct
18 Correct 12 ms 27740 KB Output is correct

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 27660 KB Output is correct
2 Correct 16 ms 27740 KB Output is correct
3 Correct 12 ms 27740 KB Output is correct
4 Correct 12 ms 27668 KB Output is correct
5 Correct 15 ms 27736 KB Output is correct
6 Correct 12 ms 27872 KB Output is correct
7 Correct 13 ms 27696 KB Output is correct
8 Correct 15 ms 27740 KB Output is correct
9 Correct 17 ms 27996 KB Output is correct
10 Correct 14 ms 27744 KB Output is correct
11 Correct 12 ms 27736 KB Output is correct
12 Correct 15 ms 27812 KB Output is correct
13 Correct 18 ms 27792 KB Output is correct
14 Correct 12 ms 27736 KB Output is correct
15 Correct 13 ms 27672 KB Output is correct
16 Correct 10 ms 27740 KB Output is correct
17 Correct 17 ms 27740 KB Output is correct
18 Correct 12 ms 27740 KB Output is correct
19 Correct 13 ms 27736 KB Output is correct
20 Correct 12 ms 27664 KB Output is correct
21 Correct 13 ms 27740 KB Output is correct
22 Correct 13 ms 27848 KB Output is correct
23 Correct 12 ms 27736 KB Output is correct
24 Correct 12 ms 27736 KB Output is correct
25 Correct 18 ms 27996 KB Output is correct
26 Correct 13 ms 27740 KB Output is correct
27 Correct 12 ms 27740 KB Output is correct
28 Correct 14 ms 27836 KB Output is correct
29 Correct 14 ms 27992 KB Output is correct
30 Correct 15 ms 27996 KB Output is correct
31 Correct 14 ms 27996 KB Output is correct
32 Correct 14 ms 27868 KB Output is correct
33 Correct 17 ms 27996 KB Output is correct
34 Correct 13 ms 27996 KB Output is correct
35 Correct 12 ms 27992 KB Output is correct
36 Correct 12 ms 27808 KB Output is correct
37 Correct 14 ms 27996 KB Output is correct
38 Correct 13 ms 27996 KB Output is correct

Subtask #3
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 27660 KB Output is correct
2 Correct 16 ms 27740 KB Output is correct
3 Correct 12 ms 27740 KB Output is correct
4 Correct 12 ms 27668 KB Output is correct
5 Correct 15 ms 27736 KB Output is correct
6 Correct 12 ms 27872 KB Output is correct
7 Correct 13 ms 27696 KB Output is correct
8 Correct 15 ms 27740 KB Output is correct
9 Correct 17 ms 27996 KB Output is correct
10 Correct 14 ms 27744 KB Output is correct
11 Correct 12 ms 27736 KB Output is correct
12 Correct 15 ms 27812 KB Output is correct
13 Correct 18 ms 27792 KB Output is correct
14 Correct 12 ms 27736 KB Output is correct
15 Correct 13 ms 27672 KB Output is correct
16 Correct 10 ms 27740 KB Output is correct
17 Correct 17 ms 27740 KB Output is correct
18 Correct 12 ms 27740 KB Output is correct
19 Correct 102 ms 33876 KB Output is correct
20 Correct 92 ms 33872 KB Output is correct
21 Correct 113 ms 34128 KB Output is correct
22 Correct 193 ms 34700 KB Output is correct
23 Correct 95 ms 34132 KB Output is correct
24 Correct 51 ms 34104 KB Output is correct
25 Correct 105 ms 38996 KB Output is correct
26 Correct 163 ms 40528 KB Output is correct
27 Runtime error 73 ms 63416 KB Execution killed with signal 11
28 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 27660 KB Output is correct
2 Correct 16 ms 27740 KB Output is correct
3 Correct 12 ms 27740 KB Output is correct
4 Correct 12 ms 27668 KB Output is correct
5 Correct 15 ms 27736 KB Output is correct
6 Correct 12 ms 27872 KB Output is correct
7 Correct 13 ms 27696 KB Output is correct
8 Correct 15 ms 27740 KB Output is correct
9 Correct 17 ms 27996 KB Output is correct
10 Correct 14 ms 27744 KB Output is correct
11 Correct 12 ms 27736 KB Output is correct
12 Correct 15 ms 27812 KB Output is correct
13 Correct 18 ms 27792 KB Output is correct
14 Correct 12 ms 27736 KB Output is correct
15 Correct 13 ms 27672 KB Output is correct
16 Correct 10 ms 27740 KB Output is correct
17 Correct 17 ms 27740 KB Output is correct
18 Correct 12 ms 27740 KB Output is correct
19 Correct 13 ms 27736 KB Output is correct
20 Correct 12 ms 27664 KB Output is correct
21 Correct 13 ms 27740 KB Output is correct
22 Correct 13 ms 27848 KB Output is correct
23 Correct 12 ms 27736 KB Output is correct
24 Correct 12 ms 27736 KB Output is correct
25 Correct 18 ms 27996 KB Output is correct
26 Correct 13 ms 27740 KB Output is correct
27 Correct 12 ms 27740 KB Output is correct
28 Correct 14 ms 27836 KB Output is correct
29 Correct 14 ms 27992 KB Output is correct
30 Correct 15 ms 27996 KB Output is correct
31 Correct 14 ms 27996 KB Output is correct
32 Correct 14 ms 27868 KB Output is correct
33 Correct 17 ms 27996 KB Output is correct
34 Correct 13 ms 27996 KB Output is correct
35 Correct 12 ms 27992 KB Output is correct
36 Correct 12 ms 27808 KB Output is correct
37 Correct 14 ms 27996 KB Output is correct
38 Correct 13 ms 27996 KB Output is correct
39 Correct 102 ms 33876 KB Output is correct
40 Correct 92 ms 33872 KB Output is correct
41 Correct 113 ms 34128 KB Output is correct
42 Correct 193 ms 34700 KB Output is correct
43 Correct 95 ms 34132 KB Output is correct
44 Correct 51 ms 34104 KB Output is correct
45 Correct 105 ms 38996 KB Output is correct
46 Correct 163 ms 40528 KB Output is correct
47 Runtime error 73 ms 63416 KB Execution killed with signal 11
48 Halted 0 ms 0 KB -