oj.uz

Submission #15902

# Submission time Handle Problem Language Result Execution time Memory
15902 2015-08-01T07:00:23 Z ggoh Dreaming (IOI13_dreaming) C++
0 / 100
 29 ms 2552 KB 
#include <cstdio>
#include <cstring>
#include <vector>
#include <utility>
#include <queue>
#include <algorithm>
#include "dreaming.h"
using namespace std;
typedef pair<int,int> pi;
vector<pi> graph[105];
 
int visited[105];
int visited2[105];
 
pi get_longest(int *vis, int x){
    queue<int> q,d;
    q.push(x);
    d.push(0);
    int max = -1, maxv = -1;
    vis[x] = 1;
    while (!q.empty()) {
        int qf = q.front();
        int df = d.front();
        if(df > max){
            max = df;
            maxv = qf;
        }
        q.pop();
        d.pop();
        for (int i=0; i<graph[qf].size(); i++) {
            pi p = graph[qf][i];
            if(!vis[p.second]){
                vis[p.second] = 1;
                q.push(p.second);
                d.push(df + p.first);
            }
        }
    }
    return pi(max,maxv);
}
 
int ret1, len;
 
int dfs(int x, int d, int p, int l){
    if(x == d) return 1;
    for (int i=0; i<graph[x].size(); i++) {
        if(graph[x][i].second == p) continue;
        if(dfs(graph[x][i].second,d,x,l + graph[x][i].first)){
            ret1 = min(ret1,max(len-l,l));
            return 1;
        }
    }
    return 0;
}
 
int get_dia(int x){
    int p = get_longest(visited2,x).second;
    return get_longest(visited,p).first;
}
 
int get_rad(int x){
    int p = get_longest(visited2,x).second;
    pi dia = get_longest(visited,p);
    int q = dia.second;
    len = dia.first;
    ret1 = len;
    dfs(p,q,-1,0);
    return ret1;
}
 
int travelTime(int N, int M, int L, int* A, int* B, int* T){
    for (int i=0; i<M; i++) {
        graph[A[i]].push_back(pi(T[i],B[i]));
        graph[B[i]].push_back(pi(T[i],A[i]));
    }
    int ret = 0;
    for (int i=0; i<N; i++) {
        if(!visited[i]) ret = max(ret,get_dia(i));
    }
    memset(visited,0,sizeof(visited));
    memset(visited2,0,sizeof(visited2));
    vector<int> rad;
    for (int i=0; i<N; i++) {
        if(!visited[i]) rad.push_back(get_rad(i));
    }
    sort(rad.begin(),rad.end());
    reverse(rad.begin(),rad.end());
    if(rad.size() > 1){
        ret = max(ret,L + rad[0] + rad[1]);
    }
    if(rad.size() > 2){
        ret = max(ret,2*L + rad[1] + rad[2]);
    }
    return ret;
}

Compilation message

dreaming.cpp: In function 'pi get_longest(int*, int)':
dreaming.cpp:30:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i=0; i<graph[qf].size(); i++) {
                       ~^~~~~~~~~~~~~~~~~
dreaming.cpp: In function 'int dfs(int, int, int, int)':
dreaming.cpp:46:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0; i<graph[x].size(); i++) {
                   ~^~~~~~~~~~~~~~~~

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 29 ms 2552 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 29 ms 2552 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 29 ms 2552 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 12 ms 1152 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 29 ms 2552 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 29 ms 2552 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -