제출 #696202

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
696202		whitedragon	경주 (Race) (IOI11_race)	C++17	43 / 100	3053 ms	43272 KiB

race

#include "race.h"
#include<iostream>
#include<vector>
 
using namespace std;
 
#define ll long long
 
ll INF;
ll min_cost;
 
struct vertex
{
    int y;
    ll 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, ll k,
vector<int>& dead_ver, vector<ll>& lvl, vector<ll>& paths_of_length, vector<ll>& 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]]<<endl;
    }
 
    for(int i=0;i<con[x].size();i++)
    {
        int y=con[x][i].y;
        ll 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<ll>& lvl,
vector<ll>& cost_of_way, vector<ll>& paths_of_length, vector<int>& dead_ver, ll 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<ll>& lvl, int k,
 vector<ll>& cost_of_way)
{
    vector<ll> paths_of_length(k+1,INF);
    //vector<ll> 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;
        ll 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;
    ll 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;
 
    while (dead_count!=n)
    {
        vector<int> visited(n+1,0);
        vector<int> sub_tree(n+1,0);
        vector<int> father(n+1);
        vector<ll> lvl(n+1);
        vector<int> visited_1(n+1,0);
        vector<int> visited_2(n+1,0);
        vector<ll> cost_of_way(n+1,INF);
 
        //cout<<"turnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn"<<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<<"centrrr "<<cen_id<<endl;
            count_from_centr(cen_id,visited_1,visited_2,con,dead_ver,lvl,k,cost_of_way);
 
            //remove
            dead_ver[cen_id]=1;
            dead_count++;
        }
    }
 
    if(min_cost==INF)
    {
        return -1;
    }
 
    return min_cost;
    
}

컴파일 시 표준 에러 (stderr) 메시지

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>&, long long int, std::vector<int>&, std::vector<long long int>&, std::vector<long long int>&, std::vector<long long int>&)':
race.cpp:70:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<vertex>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |     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<long long int>&, std::vector<long long int>&, std::vector<long long int>&, std::vector<int>&, long long int)':
race.cpp:94:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<vertex>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |     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<long long int>&, int, std::vector<long long 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++)
      |                 ~^~~~~~~~~~~~~~

• Subtask 1: 9 / 9
• Subtask 2: 12 / 12
• Subtask 3: 22 / 22
• Subtask 4: 0 / 57