oj.uz

Submission #831865

# Submission time Handle Problem Language Result Execution time Memory
831865 2023-08-20T16:21:21 Z beaconmc Factories (JOI14_factories) C++14
0 / 100
 2029 ms 55780 KB 
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>

typedef long long ll;
using namespace std;
//using namespace __gnu_pbds;

#define FOR(i, x, y) for(ll i=x; i<y; i++)
#define FORNEG(i, x, y) for(ll i=x; i>y; i--)
//#define ordered_set tree<ll, null_type,less_equal<ll>, rb_tree_tag,tree_order_statistics_node_update>
#define fast() ios_base::sync_with_stdio(false);cin.tie(NULL)

#include "factories.h"

ll dp[100001];
ll dp2[100001];
ll par[100001];

vector<vector<ll>> edges[100001];

ll n;
void Init(int N, int A[], int B[], int D[]) {
  n = N;
  FOR(i,0,N) dp[i] = 0,dp2[i] = 0;


  FOR(i,0,N-1){
    edges[B[i]].push_back({A[i], D[i]});
    edges[A[i]].push_back({B[i], D[i]});
  }

}
set<ll> first, second;
void dfs(ll a, ll p){

  par[a] = p;
  ll ans1 = 10000000000;
  ll ans2 = 10000000000;

  for (auto&i : edges[a]){
    if (i[0]==p) continue;
    dfs(i[0], a);
    ans1 = min(ans1, dp[i[0]] + i[1]);
    ans2 = min(ans2, dp2[i[0]] + i[1]);
  }
  if (first.count(a)) ans1 = 0;
  if (second.count(a)) ans2 = 0;
  dp[a] = ans1;
  dp2[a] = ans2;

}


long long Query(int S, int X[], int T, int Y[]) {
  first.clear(); second.clear();

  
  FOR(i,0,S) first.insert(X[i]);
  FOR(i,0,T) second.insert(Y[i]);
  dfs(0, -1);

  ll ans = 1000000000;
  FOR(i,0,n){
    ans = min(ans, dp[i] + dp2[i]);
  }
  return ans;

}

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 3156 KB Output is correct
2 Incorrect 2029 ms 21164 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 2884 KB Output is correct
2 Runtime error 240 ms 55780 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 3156 KB Output is correct
2 Incorrect 2029 ms 21164 KB Output isn't correct
3 Halted 0 ms 0 KB -