제출 #735117

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
735117		sandry24	꿈 (IOI13_dreaming)	C++17	14 / 100	242 ms	24716 KiB

dreaming

#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std;

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pi;
#define pb push_back
#define mp make_pair
#define f first
#define s second

vector<vector<pi>> adj(1e5+5);
vector<bool> visited(1e5+5);
vi parent(1e5+5);

ll maxe = -1, maxnode = -1;

map<pi, int> cost;

void dfs(ll x, ll p=-1, ll dist=0){
    visited[x] = 1;
    parent[x] = p;
    if(dist > maxe){
        maxe = dist;
        maxnode = x;
    }
    for(auto i : adj[x]){
        if(i.f != p)
            dfs(i.f, x, dist + i.s);
    }
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]){
    for(int i = 0; i < M; i++){
        adj[A[i]].pb({B[i], T[i]});
        adj[B[i]].pb({A[i], T[i]});
        cost[{A[i], B[i]}] = cost[{B[i], A[i]}] = T[i];
    }
    vector<pair<ll, ll>> centers;
    for(int i = 0; i < N; i++){
        if(!visited[i]){
            maxe = 0, maxnode = -1;
            dfs(i);
            if(maxnode == -1){
                centers.pb({0, i});
                continue;
            }
            ll n1 = maxnode;
            maxe = 0, maxnode = -1;
            dfs(n1);
            ll n2 = maxnode;
            vi path;
            while(n2 != n1){
                path.pb(n2);
                n2 = parent[n2];
            }
            path.pb(n2);
            ll cur = 0, best_res = 1e18, best_v = path[0];
            for (int j = 1; j < path.size(); j++) {
                cur += cost[{path[j], path[j - 1]}];
                //cout << cur << '\n';
                if (max(cur, maxe - cur) < best_res) {
                    best_res = max(cur, maxe - cur);
                    best_v = path[j];
                }
            }
            centers.push_back({best_res, best_v});
        }
    }
    /*for(auto i : centers)
        cout << i.f << ' ' << i.s << '\n';
    cout << '\n';*/
    sort(centers.begin(), centers.end(), greater<pair<ll, ll>>());
    for(int i = 1; i < centers.size(); i++){
        adj[centers[0].s].pb({centers[i].s, L});
        adj[centers[i].s].pb({centers[0].s, L});
    }
    /*for(int i = 0; i < N; i++){
        cout << i << ":\n";
        for(auto j : adj[i]){
            cout << j.f << ' ' << j.s << '\n';
        }
        cout << '\n';
    }*/
    dfs(0);
    maxe = 0;
    dfs(maxnode);
    return maxe;
}

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

dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:62:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |             for (int j = 1; j < path.size(); j++) {
      |                             ~~^~~~~~~~~~~~~
dreaming.cpp:77:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |     for(int i = 1; i < centers.size(); i++){
      |                    ~~^~~~~~~~~~~~~~~~

• Subtask 1: 14 / 14
• Subtask 2: 0 / 10
• Subtask 3: 0 / 23
• Subtask 4: 0 / 18
• Subtask 5: 0 / 12
• Subtask 6: 0 / 23