제출 #1337308

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1337308		diana	공장들 (JOI14_factories)	C++20	0 / 100	694 ms	11464 KiB

factories

#include "factories.h"
#define fi first
#define se second
#define ll long long
#define pii pair<ll, ll>
#include <bits/stdc++.h>
using namespace std;

const int M = 5e3+3, R=1e18;
int n;
vector<pii> graf[M];
bool ix[M], iy[M];
ll dx[M], dy[M];

ll dfs(int v, int p)
{
    if(!ix[v]) dx[v] = R;
    if(!iy[v]) dy[v] = R;
    ll ret = R;
    for(auto [x,d]: graf[v])
        if(x != p)
        {
            ret = min(ret, dfs(x, v));
            dx[v] = min(dx[v], dx[x]+d);
            dy[v] = min(dy[v], dy[x]+d);
        }
    ret = min(ret, dx[v]+dy[v]);
    return ret;
}


void Init(int N, int A[], int B[], int D[]) {
    n = N;
    for(int i=0; i<N; i++)
        graf[A[i]].push_back({B[i], D[i]}),
        graf[B[i]].push_back({A[i], D[i]});
}

long long Query(int S, int X[], int T, int Y[]) {
    for(int i=0; i<n; i++)
        dx[i] = dy[i] = ix[i] = iy[i] = 0;
    for(int i=0; i<S; i++)
        ix[X[i]] = 1;
    for(int j=0; j<T; j++)
        iy[Y[j]] = 1;

    return dfs(0, 0);
}

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

factories.cpp:9:24: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
    9 | const int M = 5e3+3, R=1e18;
      |                        ^~~~

• Subtask 1: 0 / 15
• Subtask 2: 0 / 18
• Subtask 3: 0 / 67