제출 #1287742

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1287742		eri16	Race (IOI11_race)	C++20	21 / 100	17 ms	8356 KiB

race

#include <bits/stdc++.h>
using namespace std;

int subtask_1(int n, int k, int v1[][2], int *v2){
    
    int psum[n+1];
    
    psum[0]=0;
    
    for (int i=1; i<=n; i++)psum[i]=psum[i-1]+v2[i-1];
    
    long long bst_ans=n+5;
    
    for (long long i=1; i<=n; i++)
        for (long long j=1; j<=n; j++)
            if (psum[j]-psum[i]==k)bst_ans=min(bst_ans,j-i);
            
    if (bst_ans==n+5)bst_ans=-1;
    return bst_ans;
}

vector<pair<int,int>> v[1005];
int visited[1005];
pair<int,int> dp[1005][1005];

void dfs(int i, int tar, int sm, int cnt){
    
    if (visited[i]==0){
    
        visited[i]=1;
        
        dp[tar][i].first=sm;
        dp[tar][i].second=cnt;
        
        for (int j=0; j<v[i].size(); j++){
            
            dfs(v[i][j].first,tar,sm+v[i][j].second,cnt+1);
            
        }
    }
}

int subtask_2(int n, int k, int v1[][2], int *v2){
    int mn_ans=n+5;
        
    for (int i=0; i<n; i++){dp[i][i].first=0;dp[i][i].second=0;}
    
    for (int i=0; i<n-1; i++){
        v[v1[i][0]].push_back({v1[i][1],v2[i]});
        v[v1[i][1]].push_back({v1[i][0],v2[i]});
    }
    
    for (int i=0; i<n; i++){
        for (int j=0; j<n; j++){
            visited[j]=0;
        }
        dfs(i,i,0,0);
    }
    
    for (int i=0; i<n; i++){
        for (int j=0; j<n; j++){
            if (dp[i][j].first==k){mn_ans=min(mn_ans,dp[i][j].second);}
        }
    }
    
    if (mn_ans==n+5){mn_ans=-1;}
    return mn_ans;
}

int best_path(int n, int k, int v1[][2], int *v2){
    
    int sbtsk_1=1;
    
    for (int i=0; i<n-1; i++){
        if (v1[i][0]!=v1[i][1]-1){
            sbtsk_1=0;
        }
    }
    
    if (sbtsk_1){
        return(subtask_1(n,k,v1,v2));
    }
    
    else if (n<=1000 && k<=1000000){
        return(subtask_2(n,k,v1,v2));
    }
       
    return -1;
    
}

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