oj.uz

Submission #703836

# Submission time Handle Problem Language Result Execution time Memory
703836 2023-02-28T15:25:52 Z Chal1shkan Parkovi (COCI22_parkovi) C++14
10 / 110
 325 ms 14196 KB 
# include <bits/stdc++.h>
 
# define pb push_back
# define ff first
# define ss second
# define nl "\n"
# define sz(x) ((int)(x).size())
# define deb(x) cerr << #x  << " = " << x << endl; 
# define pll pair <ll, ll>

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
 
const ll maxn = 2e5 + 25;
const ll inf = 1e18 + 0;
const ll mod = 1e9 + 7;
const ll dx[] = {-1, 1, 0, 0};
const ll dy[] = {0, 0, -1, 1};
 
using namespace std;

ll n, k, mx;
vector <pll> g[maxn];
ll dist[maxn];

void dijkstra (int st)
{
	dist[st] = 0;
	set <pair <ll, ll> > q;
	q.insert({0LL, st});
	while (!q.empty())
	{
		ll v = q.begin() -> ss;
		q.erase(q.begin());
		for (auto i : g[v])
		{
			ll to = i.ff, w = i.ss;
			if (dist[to] > dist[v] + w)
			{
				q.erase({dist[to], to});
				dist[to] = dist[v] + w;
				q.insert({dist[to], to});
			}
		}
	}
}

void ma1n (/* SABR */)
{
	cin >> n >> k;
	for (ll i = 1, u, v, w; i < n; ++i)
	{
		cin >> u >> v >> w;
		g[u].pb({v, w});
		g[v].pb({u, w});
	}
	if (n <= 20)
	{
		ll ans = inf, ans_mask = 0;
		for (ll mask = 0; mask < (1LL << n); ++mask)
		{
			if (__builtin_popcount(mask) == k)
			{
				for (ll i = 1; i <= n; ++i)
				{
					dist[i] = inf;
				}
				for (ll i = 0; i < n; ++i)
				{
					if (mask & (1LL << i))
					{
						dijkstra(i + 1);
					}
				}
				mx = 0;
				for (ll i = 1; i <= n; ++i)
				{
					mx = max(mx, dist[i]);
				}
				if (mx < ans)
				{
					ans = mx;
					ans_mask = mask;
				}
			}
		}
		cout << ans << nl;
		for (ll i = 0; i < n; ++i)
		{
			if (ans_mask & (1LL << i))
			{
				cout << i + 1 << ' ';
			}
		}
		cout << nl;
	}
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
//  freopen("file.in", "r", stdin);
//  freopen("file.out", "w", stdout);
    int ttt = 1;	
//  cin >> ttt;
    for (int test = 1; test <= ttt; ++test)
    {
//      cout << "Case " << test << ":" << ' ';
        ma1n();
    }
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4948 KB Output is correct
2 Correct 7 ms 4948 KB Output is correct
3 Correct 8 ms 5024 KB Output is correct
4 Correct 5 ms 4948 KB Output is correct
5 Correct 6 ms 5020 KB Output is correct
6 Correct 68 ms 5004 KB Output is correct
7 Correct 62 ms 5020 KB Output is correct
8 Correct 19 ms 4948 KB Output is correct
9 Correct 325 ms 5000 KB Output is correct
10 Correct 20 ms 4948 KB Output is correct
11 Correct 169 ms 4948 KB Output is correct
12 Correct 283 ms 5000 KB Output is correct
13 Correct 9 ms 4948 KB Output is correct
14 Correct 154 ms 5004 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 53 ms 13728 KB Unexpected end of file - int64 expected
2 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 63 ms 14196 KB Unexpected end of file - int64 expected
2 Halted 0 ms 0 KB -

Subtask #4
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4948 KB Output is correct
2 Correct 7 ms 4948 KB Output is correct
3 Correct 8 ms 5024 KB Output is correct
4 Correct 5 ms 4948 KB Output is correct
5 Correct 6 ms 5020 KB Output is correct
6 Correct 68 ms 5004 KB Output is correct
7 Correct 62 ms 5020 KB Output is correct
8 Correct 19 ms 4948 KB Output is correct
9 Correct 325 ms 5000 KB Output is correct
10 Correct 20 ms 4948 KB Output is correct
11 Correct 169 ms 4948 KB Output is correct
12 Correct 283 ms 5000 KB Output is correct
13 Correct 9 ms 4948 KB Output is correct
14 Correct 154 ms 5004 KB Output is correct
15 Incorrect 53 ms 13728 KB Unexpected end of file - int64 expected
16 Halted 0 ms 0 KB -