Submission #62030

#	Time	Username	Problem	Language	Result	Execution time	Memory
62030		Darksinian	Factories (JOI14_factories)	C++14	0 / 100	20 ms	2976 KiB

factories

#include "factories.h"
#include<bits/stdc++.h>
using namespace std;
long long dp[100002][3];
int c[100002];
int n;
vector<pair<int,int> > g[100002];
void dfs(int s,int p) {
    dp[s][1] = 1e17;
    dp[s][2] = 1e17;
    if(c[s]) dp[s][c[s]] = 0;
    for(auto u : g[s]) {
        int u1 = u.first;
        if(u1!=p) {
            dfs(u1,s);
            dp[s][1] = min(dp[s][1],dp[u1][1] + u.second);
            dp[s][2] = min(dp[s][2],dp[u1][2] + u.second);
        }
    }
}
void Init(int N, int A[], int B[], int D[]) {
    n = N;
    for(int i =0;i<N;i++){
        g[A[i]].push_back({B[i],D[i]});
        g[B[i]].push_back({A[i],D[i]});
    }
}

long long Query(int S, int X[], int T, int Y[]) {
  for(int i =0;i<S;i++) {
    c[X[i]] = 1;
  }
  for(int i =0;i<T;i++){
    c[Y[i]] = 2;
  }
  dfs(0,0);
  for(int i =0;i<n;i++) c[i] = 0;
  long long ans = 1e18;
  for(int i =0;i<n;i++) ans = min(ans,dp[i][1] + dp[i][2]);
  return 0;
}

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