oj.uz

Submission #1033537

# Submission time Handle Problem Language Result Execution time Memory
1033537 2024-07-25T03:13:02 Z ezzzay Dreaming (IOI13_dreaming) C++14
0 / 100
 1000 ms 16596 KB 
#include "dreaming.h"
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define ff first
#define ss second
const int MN=3e5+5;;
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[]) {
    for(int i=0;i<N;i++)vis[i]=0;
    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){
                for(int j=0;j<N;j++){
                    dist[j]=0;
                }
                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

# Verdict Execution time Memory Grader output
1 Execution timed out 1063 ms 16596 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 7260 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1063 ms 16596 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 501 ms 11232 KB Output is correct
2 Correct 482 ms 10976 KB Output is correct
3 Correct 436 ms 10944 KB Output is correct
4 Correct 509 ms 10976 KB Output is correct
5 Correct 459 ms 10960 KB Output is correct
6 Correct 548 ms 11456 KB Output is correct
7 Correct 458 ms 11476 KB Output is correct
8 Correct 452 ms 10996 KB Output is correct
9 Correct 463 ms 10960 KB Output is correct
10 Correct 492 ms 11092 KB Output is correct
11 Correct 3 ms 7260 KB Output is correct
12 Correct 545 ms 8676 KB Output is correct
13 Correct 504 ms 8652 KB Output is correct
14 Correct 544 ms 8476 KB Output is correct
15 Correct 485 ms 8652 KB Output is correct
16 Correct 482 ms 8396 KB Output is correct
17 Correct 501 ms 8416 KB Output is correct
18 Correct 463 ms 8708 KB Output is correct
19 Correct 484 ms 8396 KB Output is correct
20 Incorrect 3 ms 7260 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 7260 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1063 ms 16596 KB Time limit exceeded
2 Halted 0 ms 0 KB -