제출 #153811

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
153811		popovicirobert	꿈 (IOI13_dreaming)	C++14	47 / 100	171 ms	16372 KiB

dreaming

#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 = 0; 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(ans <= dstA[b] && (i == 1 || dstA[b] >= l + dst + cur_dst)) {
            ans = dstA[b];
            nod = cur_nod;
            dst = cur_dst;
        }
        else if(ans <= l + dst + cur_dst) {
            ans = l + dst + cur_dst;
            cur_dst = dst + l;
            dst = max(dst, ans - dst);

            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;
                    }
                }
            }
        }

        /*cerr << ans << " " << dst << " " << nod << "\n";
        for(auto it : nodes) {
            cerr << it << " " << on_way[it] << "\n";
        }
        cerr << "\n";*/

    }
    return ans;
}

컴파일 시 표준 에러 (stderr) 메시지

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: 14 / 14
• Subtask 2: 10 / 10
• Subtask 3: 23 / 23
• Subtask 4: 0 / 18
• Subtask 5: 0 / 12
• Subtask 6: 0 / 23