| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 101215 |
2019-03-17T14:25:05 Z |
davitmarg |
Race (IOI11_race) |
C++17 |
|
7 ms |
5120 KB |
/*DavitMarg*/
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <iterator>
#include <ctype.h>
#include <stdlib.h>
#include <cassert>
#include <fstream>
#ifndef death
#include "race.h"
#endif
#define mod 1000000007ll
#define LL long long
#define LD long double
#define MP make_pair
#define PB push_back
#define all(v) v.begin(),v.end()
using namespace std;
int n, k, num[200005], used[200005], usedNum[200005], usedC[200005], wasC[200005], color = 1, cColor = 1, numColor = 1, ans = mod;
vector<pair<int, LL>> g[200005], upd;
vector<int> cl;
int dp[1000006];
void getNum(int v)
{
usedNum[v] = numColor;
num[v] = 1;
for (int i = 0; i < g[v].size(); i++)
{
int to = g[v][i].first;
if (usedNum[to] == numColor || wasC[to])
continue;
getNum(to);
num[v] += num[to];
}
}
int centroid(int v)
{
numColor++;
cColor++;
getNum(v);
int st = v;
queue<int> q;
q.push(v);
while (!q.empty())
{
v = q.front();
q.pop();
usedC[v] = cColor;
bool is = 1;
for (int i = 0; i<g[v].size(); i++)
if (num[g[v][i].first]>num[st] / 2 && usedC[g[v][i].first] != cColor && !wasC[g[v][i].first])
{
is = 0;
q.push(g[v][i].first);
}
if (is)
{
wasC[v] = 1;
return v;
}
}
}
void dfs(int v, LL sum, int depth)
{
used[v] = color;
if (dp[sum] == 0)
dp[sum] = mod;
if (k > sum && dp[k - sum] == 0)
dp[k - sum] = mod;
if (sum == k)
ans = min(ans, depth);
else if (sum < k)
ans = min(ans, depth + dp[k - sum]);
else
return;
upd.PB(MP(depth, sum));
if(sum<=k)
cl.PB(v);
for (int i = 0; i < g[v].size(); i++)
{
int to = g[v][i].first;
LL D = g[v][i].second;
if (used[to] == color || wasC[to])
continue;
dfs(to, sum + D, depth + 1);
}
}
void solve(int v)
{
color++;
vector<int> nxt;
for (int i = 0; i < g[v].size(); i++)
{
int to = g[v][i].first;
LL D = g[v][i].second;
if (used[to] == color || wasC[to])
continue;
upd.clear();
dfs(to, D, 1);
for (int j = 0; j < upd.size(); j++)
dp[upd[j].second] = min(dp[upd[j].second], upd[j].first);
nxt.PB(to);
}
while (!cl.empty())
{
dp[cl.back()] = 0;
cl.pop_back();
}
for (int i = 0; i < nxt.size(); i++)
solve(centroid(nxt[i]));
}
int Main()
{
solve(centroid(1));
if (ans == mod)
ans = -1;
return 0;
}
int best_path(int N, int K, int h[][2], int l[])
{
n = N;
k = K;
for (int i = 0; i < n - 1; i++)
{
h[i][0]++;
h[i][1]++;
g[h[i][0]].PB(MP(h[i][1], l[i]));
g[h[i][1]].PB(MP(h[i][0], l[i]));
}
Main();
return ans;
}
#ifdef death
int main()
{
cin >> n >> k;
for (int i = 0; i < n - 1; i++)
{
int a, b;
LL D;
cin >> a >> b >> D;
/*a = i;
b = a + 1;
D = rand() % 20;*/
a++;
b++;
g[a].PB(MP(b, D));
g[b].PB(MP(a, D));
}
Main();
cout << ans << endl;
return 0;
}
#endif
/*
*/
Compilation message
race.cpp: In function 'void getNum(int)':
race.cpp:39:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < g[v].size(); i++)
~~^~~~~~~~~~~~~
race.cpp: In function 'int centroid(int)':
race.cpp:63:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i<g[v].size(); i++)
~^~~~~~~~~~~~
race.cpp: In function 'void dfs(int, long long int, int)':
race.cpp:97:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < g[v].size(); i++)
~~^~~~~~~~~~~~~
race.cpp: In function 'void solve(int)':
race.cpp:111:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < g[v].size(); i++)
~~^~~~~~~~~~~~~
race.cpp:120:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = 0; j < upd.size(); j++)
~~^~~~~~~~~~~~
race.cpp:129:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < nxt.size(); i++)
~~^~~~~~~~~~~~
race.cpp: In function 'int centroid(int)':
race.cpp:75:1: warning: control reaches end of non-void function [-Wreturn-type]
}
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
5120 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
5120 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
5120 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
5120 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
