oj.uz

답안 #153803

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
153803 2019-09-16T13:52:07 Z popovicirobert 꿈 (IOI13_dreaming) C++14
0 / 100
 1000 ms 15476 KB 
#include "dreaming.h"
#include <bits/stdc++.h>

using namespace std;

const int INF = 2e9;
const int MAXN = (int) 1e5;

static vector < pair <int, int> > g[MAXN + 1];
static int dstA[MAXN + 1], dstB[MAXN + 1];
static bool vis[MAXN + 1], on_way[MAXN + 1];
static vector <int> nodes;

void dfs(int nod, int par, int *dst) {
    if(vis[nod] == 0) {
        nodes.push_back(nod);
    }
    vis[nod] = 1;
    for(auto it : g[nod]) {
        if(it.first != par) {
            dst[it.first] = dst[nod] + it.second;
            dfs(it.first, nod, dst);
        }
    }
}

int travelTime(int n, int m, int l, int A[], int B[], int T[]) {
    int i;
    for(i = 1; i <= m; i++) {
        A[i]++, B[i]++;
        g[A[i]].push_back({B[i], T[i]});
        g[B[i]].push_back({A[i], T[i]});
    }

    int nod = 0, dst = 0, ans = 0;
    for(i = 1; i <= n; i++) {
        if(vis[i]) continue;

        nodes.clear();
        dfs(i, 0, dstA);
        int a = 0;
        for(auto it : nodes) {
            if(dstA[it] >= dstA[a]) {
                a = it;
            }
        }
        dstA[a] = 0;
        dfs(a, 0, dstA);

        int b = 0;
        for(auto it : nodes) {
            if(dstA[it] >= dstA[b]) {
                b = it;
            }
        }
        dfs(b, 0, dstB);

        int cur_nod, cur_dst = INF;
        int id;

        for(auto it : nodes) {
            if(cur_dst >= max(dstA[it], dstB[it])) {
                cur_dst = max(dstA[it], dstB[it]);
                if(cur_dst == dstA[it]) {
                    id = a;
                }
                else {
                    id = b;
                }
                cur_nod = it;
            }
        }

        int aux = cur_nod;
        while(aux != id) {
            on_way[aux] = 1;
            for(auto it : g[aux]) {
                if(id == a) {
                    if(dstA[it.first] + it.second == dstA[aux]) {
                        aux = it.first;
                        break;
                    }
                }
                else {
                    if(dstB[it.first] + it.second == dstB[aux]) {
                        aux = it.first;
                        break;
                    }
                }
            }
        }
        on_way[id] = 1;

        if(nod > 0 && ans <= l + dst + cur_dst) {
            ans = l + dst + cur_dst;
            cur_dst += l;

            while(dst >= max(cur_dst, ans - cur_dst)) {
                nod = cur_nod;
                dst = max(cur_dst, ans - cur_dst);
                for(auto it : g[nod]) {
                    if(on_way[it.first]) {
                        cur_nod = it.first;
                        cur_dst += it.second;
                        break;
                    }
                }
            }
        }
        if(ans <= dstA[b]) {
            ans = dstA[b];
            nod = cur_nod;
            dst = cur_dst;
        }
    }
    return ans;
}

Compilation message

dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:78:17: warning: 'id' may be used uninitialized in this function [-Wmaybe-uninitialized]
                 if(id == a) {
                 ^~
dreaming.cpp:92:20: warning: 'cur_nod' may be used uninitialized in this function [-Wmaybe-uninitialized]
         on_way[id] = 1;
         ~~~~~~~~~~~^~~

Subtask #1
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1067 ms 15476 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1067 ms 15476 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1067 ms 15476 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1056 ms 5408 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1067 ms 15476 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1067 ms 15476 KB Time limit exceeded
2 Halted 0 ms 0 KB -