Submission #1337320

#	Time	Username	Problem	Language	Result	Execution time	Memory
1337320		diana	Factories (JOI14_factories)	C++20	0 / 100	675 ms	11300 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=1e16;
int n;
vector<pii> graf[M];
bool ix[M], iy[M];
ll dx[M], dy[M];
ll ans;

void dfs(int v, int p)
{
    if(ix[v]) dx[v] = 0;
    if(iy[v]) dy[v] = 0;
    for(auto [u,d]: graf[v])
        if(u != p)
        {
            dfs(u, v);
            dx[v] = min(dx[v], dx[u]+d);
            dy[v] = min(dy[v], dy[u]+d);
        }
    ans = min(ans, dx[v]+dy[v]);
}


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] = R,
        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;
    ans = R;
    dfs(0, 0);
    return ans;
}

Compilation message (stderr)

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

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