제출 #1081145

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1081145		alexander707070	도로 폐쇄 (APIO21_roads)	C++14	0 / 100	2081 ms	22688 KiB

roads

#include<bits/stdc++.h>
#include "roads.h"

#define MAXN 100007
using namespace std;

const long long inf=1e10;

int n,a,b,k;
vector< pair<int,int> > v[MAXN];

long long dp[MAXN][2];
int li[MAXN][2],tim;

long long ff(int x,int p,bool par){

    if(li[x][par]==tim)return dp[x][par];
    li[x][par]=tim;
    dp[x][par]=0;

    vector<long long> s;
    for(int i=0;i<v[x].size();i++){

        if(v[x][i].first==p){
            if(par)dp[x][par]+=v[x][i].second;
            continue;
        }

        s.push_back(ff(v[x][i].first,x,true)-ff(v[x][i].first,x,false));
        dp[x][par]+=ff(v[x][i].first,x,false);
    }

    sort(s.begin(),s.end());

    if(k==0 and !par and x!=1){
        dp[x][par]=inf;
        return inf;
    }

    for(int i=0;i<int(v[x].size())-k-par;i++){
        dp[x][par]+=s[i];
    }

    return dp[x][par];
}

vector<long long> minimum_closure_costs(int N,vector<int> U,vector<int> V,vector<int> W){
    n=N;

    for(int i=1;i<=n-1;i++){
        a=U[i-1]; b=V[i-1];
        a++; b++;

        v[a].push_back({b,W[i-1]});
        v[b].push_back({a,W[i-1]});
    }

    vector<long long> res;

    for(int i=0;i<=n-1;i++){     
        k=i; tim++;
        res.push_back(ff(1,0,0));
    }

    return res;
}

/*int main(){

    //vector<long long> s=minimum_closure_costs(5, {0, 0, 0, 2}, {1, 2, 3, 4}, {1, 4, 3, 2});
    vector<long long> s=minimum_closure_costs(4, {0, 2, 0}, {1, 0, 3}, {5, 10, 5});

    for(long long i:s)cout<<i<<" ";

    return 0;
}*/

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

roads.cpp: In function 'long long int ff(int, int, bool)':
roads.cpp:22:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |     for(int i=0;i<v[x].size();i++){
      |                 ~^~~~~~~~~~~~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 7
• Subtask 3: 0 / 14
• Subtask 4: 0 / 10
• Subtask 5: 0 / 17
• Subtask 6: 0 / 25
• Subtask 7: 0 / 22