| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 696184 |
2023-02-05T18:07:27 Z |
whitedragon |
Race (IOI11_race) |
C++17 |
|
1 ms |
468 KB |
#include "race.h"
#include<iostream>
#include<vector>
using namespace std;
#define ll long long
int INF;
int min_cost;
struct vertex
{
int y;
int cost;
};
void dfs_1(int x, vector<int>& visited, vector<vector<vertex>>& con,
vector<int>& sub_tree, vector<int>& father, vector<int>& dead_ver)
{
//cout<<"#"<<x<<endl;
visited[x]=1;
for(int i=0;i<con[x].size();i++)
{
int y=con[x][i].y;
//int cost=con[x][i].cost;
if(dead_ver[y]!=1 && visited[y]==0)
{
father[y]=x;
dfs_1(y,visited,con,sub_tree,father,dead_ver);
sub_tree[x]+=sub_tree[y]+1;
}
}
//cout<<"#"<<x<<" "<<sub_tree[x]<<endl;
}
int find_centr(int x, vector<vector<vertex>>& con, vector<int>& sub_tree,
vector<int>& father, vector<int>& dead_ver, int tree_size)
{
for(int i=0;i<con[x].size();i++)
{
int y=con[x][i].y;
if(dead_ver[y]!=1 && father[x]!=y && sub_tree[y]+1>(tree_size/2))
{
//cout<<"^"<<y<<" "<<sub_tree[y]+1<<" "<<tree_size<<endl;
return find_centr(y,con,sub_tree,father,dead_ver,tree_size);
}
}
return x;
}
void dfs_2(int x, vector<vector<vertex>>& con, vector<int>& visited, int k,
vector<int>& dead_ver, vector<int>& lvl, vector<int>& paths_of_length, vector<int>& cost_of_way)
{
visited[x]=1;
//cout<<"&&"<<x<<endl;
if(cost_of_way[x]<=k)
{
//caly koszt to najmniejszy dojsuca wczesniej + moj
min_cost=min(min_cost,lvl[x]+paths_of_length[k-cost_of_way[x]]);
//cout<<"cost kannnnnnnnn "<<lvl[x]<<" "<<paths_of_length[k-cost_of_way[x]]<<" "<<
//cost_of_way[x]<<endl;
}
for(int i=0;i<con[x].size();i++)
{
int y=con[x][i].y;
int cost=con[x][i].cost;
if(dead_ver[y]!=1 && visited[y]==0)
{
lvl[y]=lvl[x]+1;
cost_of_way[y]=cost_of_way[x]+cost;
dfs_2(y,con,visited,k,dead_ver,lvl,paths_of_length,cost_of_way);
}
}
}
void dfs_3(int x, vector<vector<vertex>>& con, vector<int>& visited, vector<int>& lvl,
vector<int>& cost_of_way, vector<int>& paths_of_length, vector<int>& dead_ver, int k)
{
visited[x]=1;
if(cost_of_way[x]<=k)
{
paths_of_length[cost_of_way[x]]=min(paths_of_length[cost_of_way[x]],lvl[x]);
}
for(int i=0;i<con[x].size();i++)
{
int y=con[x][i].y;
if(dead_ver[y]!=1 && visited[y]==0)
{
dfs_3(y,con,visited,lvl,cost_of_way,paths_of_length,dead_ver,k);
}
}
}
void count_from_centr(int x, vector<int>& visited_1, vector<int>& visited_2,
vector<vector<vertex>>& con,vector<int>& dead_ver, vector<int>& lvl, int k)
{
vector<int> paths_of_length(k+1,INF);
vector<int> cost_of_way(k+1,INF);
paths_of_length[0]=0;
lvl[x]=0;
cost_of_way[x]=0;
visited_1[x]=1;
visited_2[x]=1;
for(int i=0;i<con[x].size();i++)
{
int y=con[x][i].y;
int cost=con[x][i].cost;
if(dead_ver[y]!=1 && visited_1[y]==0)
{
lvl[y]=1;
cost_of_way[y]=cost;
//cout<<"&"<<y<<endl;
//dfs2
dfs_2(y,con,visited_1,k,dead_ver,lvl,paths_of_length,cost_of_way);
//dfs3
dfs_3(y,con,visited_2,lvl,cost_of_way,paths_of_length,dead_ver,k);
}
}
}
int best_path(int N, int K, int H[][2], int L[])
{
int n=N;
int k=K;
min_cost=n+1;
INF=n+1;
vector<vector<vertex>> con(n+1);
for(int i=0;i<n-1;i++)
{
int a=H[i][0];
int b=H[i][1];
a++;
b++;
//cout<<a<<" "<<b<<" "<<L[i]<<endl;
vertex A;
A.y=b;
A.cost=L[i];
con[a].push_back(A);
vertex B;
B.y=a;
B.cost=L[i];
con[b].push_back(B);
}
vector<int> dead_ver(n+1,0);
int dead_count=0;
//cout<<endl;
while (dead_count!=n)
{
vector<int> visited(n+1,0);
vector<int> sub_tree(n+1,0);
vector<int> father(n+1);
vector<int> lvl(n+1);
vector<int> visited_1(n+1,0);
vector<int> visited_2(n+1,0);
//cout<<"turnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn"<<endl;
//cout<<1<<endl;
for(int x=1;x<=n;x++)
{
if(visited[x]!=0)
{
continue;
}
if(dead_ver[x]==1)
{
continue;
}
father[x]=x;
//cout<<"dfsssssssssssssssssssssssssss"<<endl;
dfs_1(x,visited,con,sub_tree,father,dead_ver);
int cen_id=find_centr(x,con,sub_tree,father,dead_ver,sub_tree[x]+1);
//cout<<1;
count_from_centr(cen_id,visited_1,visited_2,con,dead_ver,lvl,k);
//remove
dead_ver[cen_id]=1;
dead_count++;
}
}
//cout<<1<<endl;
if(min_cost==INF)
{
return -1;
}
return min_cost;
}
Compilation message
race.cpp: In function 'void dfs_1(int, std::vector<int>&, std::vector<std::vector<vertex> >&, std::vector<int>&, std::vector<int>&, std::vector<int>&)':
race.cpp:24:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<vertex>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
24 | for(int i=0;i<con[x].size();i++)
| ~^~~~~~~~~~~~~~
race.cpp: In function 'int find_centr(int, std::vector<std::vector<vertex> >&, std::vector<int>&, std::vector<int>&, std::vector<int>&, int)':
race.cpp:43:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<vertex>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
43 | for(int i=0;i<con[x].size();i++)
| ~^~~~~~~~~~~~~~
race.cpp: In function 'void dfs_2(int, std::vector<std::vector<vertex> >&, std::vector<int>&, int, std::vector<int>&, std::vector<int>&, std::vector<int>&, std::vector<int>&)':
race.cpp:71:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<vertex>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
71 | for(int i=0;i<con[x].size();i++)
| ~^~~~~~~~~~~~~~
race.cpp: In function 'void dfs_3(int, std::vector<std::vector<vertex> >&, std::vector<int>&, std::vector<int>&, std::vector<int>&, std::vector<int>&, std::vector<int>&, int)':
race.cpp:95:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<vertex>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
95 | for(int i=0;i<con[x].size();i++)
| ~^~~~~~~~~~~~~~
race.cpp: In function 'void count_from_centr(int, std::vector<int>&, std::vector<int>&, std::vector<std::vector<vertex> >&, std::vector<int>&, std::vector<int>&, int)':
race.cpp:117:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<vertex>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
117 | for(int i=0;i<con[x].size();i++)
| ~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
