oj.uz

Submission #336038

# Submission time Handle Problem Language Result Execution time Memory
336038 2020-12-14T14:27:10 Z knightron0 Dreaming (IOI13_dreaming) C++14
0 / 100
 106 ms 15612 KB 
#include <bits/stdc++.h>
#include "dreaming.h"
#define pb push_back
#define mp make_pair
#define fr first
#define sc second
#define clr(a) memset(a, 0, sizeof(a))
#define all(v) v.begin(), v.end()

using namespace std;
const int MOD = 1e9 + 7;
const int MAXN = 1e5 + 5;

int dist[MAXN];
vector<pair<int, int> > adj[MAXN];
int n, m, k;
int mx;
int val;
bool vis[MAXN][10]; 
vector<int> nice;

void dfs(int s, int curr, int fl, bool ad){

    vis[s][fl] = true;
    if(curr >= mx){
        mx = curr;
        val = s;
    }
    if(ad){
        dist[s] = max(curr, dist[s]);
    } else {
        nice.pb(s);
    }
    for(auto it: adj[s]){
        if(!vis[it.fr][fl]){
            dfs(it.fr, curr + it.sc, fl, ad);
        }
    }
}
int travelTime(int N,int M,int L, int A[],int B[],int T[]){
    n = N; m = M; k = L;
    for(int i= 0;i<m;i++){
        adj[A[i]].pb(mp(B[i], T[i]));
        adj[B[i]].pb(mp(A[i], T[i]));
    }
    clr(dist);
    vector<pair<int, int> > vec;
    for(int i = 0;i<n;i++){
        if(vis[i][0]) continue;
        nice.clear();
        mx = 0;
        val = -1;
        dfs(i, 0, 0, 0);
        int d1 = val;
        mx = 0;
        val = -1;
        dfs(d1, 0, 1, 1);
        int d2 = val;
        mx = 0;
        val = -1;
        dfs(d2, 0, 2, 1);
        int ok = 0;
        int mxval=INT_MAX;
        for(int j: nice){
            if(dist[j] <= mxval){
                mxval = dist[j];
                ok = j;
            }
        }
        vec.pb(mp(dist[ok], ok));
    }
    sort(all(vec));
    reverse(all(vec));
    for(int i= 1;i<(int)vec.size();i++){
        adj[vec[0].sc].pb(mp(vec[i].sc, k));
    }
    mx = 0;
    val = -1;
    dfs(1, 0, 4, 0);
    int d1 = val; mx = 0; val = -1;
    dfs(d1, 0, 5, 1);
    return mx;
}
// signed main() {
//     ios_base::sync_with_stdio(false);
//     cin.tie(NULL);
//     #ifndef ONLINE_JUDGE
//     freopen("input.txt", "r", stdin);
//     #endif
    
//     return 0;
// }

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 15468 KB Output is correct
2 Correct 82 ms 15612 KB Output is correct
3 Correct 47 ms 11368 KB Output is correct
4 Correct 10 ms 4992 KB Output is correct
5 Incorrect 8 ms 4076 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 15468 KB Output is correct
2 Correct 82 ms 15612 KB Output is correct
3 Correct 47 ms 11368 KB Output is correct
4 Correct 10 ms 4992 KB Output is correct
5 Incorrect 8 ms 4076 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 15468 KB Output is correct
2 Correct 82 ms 15612 KB Output is correct
3 Correct 47 ms 11368 KB Output is correct
4 Correct 10 ms 4992 KB Output is correct
5 Incorrect 8 ms 4076 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

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

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 15468 KB Output is correct
2 Correct 82 ms 15612 KB Output is correct
3 Correct 47 ms 11368 KB Output is correct
4 Correct 10 ms 4992 KB Output is correct
5 Incorrect 8 ms 4076 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 15468 KB Output is correct
2 Correct 82 ms 15612 KB Output is correct
3 Correct 47 ms 11368 KB Output is correct
4 Correct 10 ms 4992 KB Output is correct
5 Incorrect 8 ms 4076 KB Output isn't correct
6 Halted 0 ms 0 KB -