| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 283612 |
2020-08-26T03:17:00 Z |
aloo123 |
Race (IOI11_race) |
C++14 |
|
28 ms |
47352 KB |
#include <bits/stdc++.h>
#define ll long long int
#define vi vector<int>
#define vll vector<ll>
#define vvi vector < vi >
#define pii pair<int,int>
#define pll pair<long long, long long>
#define mod 1000000007
#define inf 9999999999;
#define all(c) c.begin(),c.end()
#define mp(x,y) make_pair(x,y)
#define pb push_back
#define in insert
#define f first
#define s second
#define pi 3.141592653589793238
using namespace std;
const int MAXN = 1e6+5;
const int INF = 1e7;
int n,k;
set<int>adj[MAXN];
map<pair<int,int>,int> wt;
int sz[MAXN];
int currsize;
int ans;
int cnt[MAXN];
int glob[MAXN];
bool blocked[MAXN];
void dfs(int u,int p){
sz[u] = 1;
currsize++;
for(auto v:adj[u]){
if(v != p && !blocked[v]){
dfs(v,u);
sz[u] += sz[v];
}
}
}
int dfs2(int u,int p){
for(auto v:adj[u]){
if(v != p && sz[v] > currsize/2 && !blocked[v]){
return dfs2(v,u);
}
}
return u;
}
void dfs3(int u,int p,int sum,int dep){
if(sum <= k){
cnt[sum] = min(cnt[sum],dep);
ans = min(ans,glob[k-sum] + cnt[sum]);
}
for(auto v:adj[u]){
if(v != p && !blocked[v]){
dfs3(v,u,sum + wt[{u,v}],dep+1);
}
}
}
void decompose(int u){
currsize=0;
dfs(u,-1);
int c = dfs2(u,-1);
for(auto v:adj[c]){
if(blocked[v]) continue;
for(int i =1;i<=k;i++) cnt[i] =5*n;
dfs3(v,c,wt[{c,v}],1);
for(int i =1;i<=k;i++) {
glob[i] = min(glob[i],cnt[i]);
}
}
blocked[c] = true;
for(auto v:adj[c]){
if(blocked[v] == false)
decompose(v);
}
blocked[c] = false;
}
int best_path(int N, int K, int H[][2], int L[]){
n = N;
k = K;
ans = 5*n;
for(int i = 0;i<N-1;i++){
int u = H[i][0];
int v = H[i][1];
u++;
v++;
int w = L[i];
wt[{u,v}] = w;
wt[{v,u}] = w;
adj[u].in(v);
adj[v].in(u);
}
for(int i =1;i<=k;i++) glob[i] = (5*n);
decompose(1);
if(ans == (5*n)) ans = -1;
return ans;
}
// int main()
// {
// std::ios::sync_with_stdio(false);
// // int h[10][2];
// // h[0][0] = 0;
// // h[0][1] = 1;
// // h[1][0] = 0;
// // h[1][1] = 2;
// // h[2][0] = 2;
// // h[2][1] = 3;
// // h[3][0] = 3;
// // h[3][1] = 4;
// // h[4][0] = 4;
// // h[4][1] = 5;
// // h[5][0] = 0;
// // h[5][1] = 6;
// // h[6][0] = 6;
// // h[6][1] = 7;
// // h[7][0] = 6;
// // h[7][1] = 8;
// // h[8][0] = 8;
// // h[8][1] = 9;
// // h[9][0 ] = 8;
// // h[9][1] = 10;
// // int l[10];
// // l[0] = 3;
// // l[1] = 4;
// // l[2] = 5;
// // l[3] = 4;
// // l[4] = 6;
// // l[5] = 3;
// // l[6] = 2;
// // l[7] = 5;
// // l[8] = 6;
// // l[9] = 7;
// // int h2[2][2];
// // h2[0][0] =0;
// // h2[0][1] = 1;
// // h2[1][0] =1;
// // h2[1][1] = 2;
// // int l2[2];
// // l2[0] = 1;
// // l2[1] = 1;
// // cout << best_path(11,12,h,l) << endl;
// cin >> n;
// cin >> k;
// for(int i =2;i<=n;i++){
// int u,v;
// cin >> u >> v;
// int w;
// cin >> w;
// wt[{u,v}] = w;
// wt[{v,u}] = w;
// adj[u].in(v);
// adj[v].in(u);
// }
// ans = (5*n);
// for(int i =1;i<=k;i++) glob[i] = (5*n);
// decompose(1,-1);
// // for(int i = 1;i<=k;i++) cout << glob[i] << endl;
// if(ans == (5*n)) ans = -1;
// cout << ans << endl;
// return 0;
// }
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
28 ms |
47352 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
28 ms |
47352 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
28 ms |
47352 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
28 ms |
47352 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
