oj.uz

답안 #1033533

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1033533 2024-07-25T03:08:35 Z ezzzay 꿈 (IOI13_dreaming) C++14
0 / 100
 14 ms 3664 KB 
#include "dreaming.h"
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define ff first
#define ss second
const int MN=4000;
vector<pair<int,int>>v[MN];
bool vis[MN];
int dist[MN];
vector<int>tmp;
void df(int a){
    vis[a]=1;
    tmp.pb(a);
    for(auto p:v[a]){
        if(vis[p.ff]==0)df(p.ff);
    }
}
vector<int>vh;
int z=0;
void dfs(int a, int u){
    for(auto p:v[a]){
        int b=p.ff;
        int c=p.ss;
        if(b==u)continue;
        dist[b]=dist[a]+c;
        z=max(z,dist[b]);
        dfs(b,a);
    }
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    memset(vis,0,sizeof vis);
    for(int i=0;i<M;i++){
        v[A[i]].pb({B[i],T[i]});
        v[B[i]].pb({A[i],T[i]});
    }
    vector<int>vec;
    for(int i=0;i<N;i++){
        if(vis[i]==0){
           
            tmp.clear();
            df(i);
            int g=1e9;
            for(auto a:tmp){
                memset(dist,0,sizeof dist);
                vh.clear();
                z=0;
                dfs(a,-1);
                g=min(g,z);
            }
            vec.pb(g);
        }
    }
    sort(vec.begin(),vec.end(),greater<int>());
    if(vec.size()==2){
        return vec[0]+vec[1]+L;
    }
    else{
        return max(vec[0]+vec[1]+L,vec[1]+vec[2]+L*2);
    }
}

Subtask #1
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 14 ms 3664 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 14 ms 3664 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 7 ms 1884 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 14 ms 3664 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -