oj.uz

Submission #831870

# Submission time Handle Problem Language Result Execution time Memory
831870 2023-08-20T16:29:03 Z beaconmc Factories (JOI14_factories) C++14
15 / 100
 2919 ms 37092 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 = 1000000000000000;
  ll ans2 = 1000000000000000;

  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 = 1000000000000000;
  FOR(i,0,n){
    ans = min(ans, dp[i] + dp2[i]);
  }
  return ans;

}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 3028 KB Output is correct
2 Correct 1994 ms 11584 KB Output is correct
3 Correct 2919 ms 20968 KB Output is correct
4 Correct 2391 ms 21160 KB Output is correct
5 Correct 2028 ms 21468 KB Output is correct
6 Correct 1268 ms 20992 KB Output is correct
7 Correct 2905 ms 20928 KB Output is correct
8 Correct 2452 ms 21212 KB Output is correct
9 Correct 2136 ms 21352 KB Output is correct
10 Correct 1311 ms 21016 KB Output is correct
11 Correct 2911 ms 20888 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 2772 KB Output is correct
2 Runtime error 218 ms 37092 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 3028 KB Output is correct
2 Correct 1994 ms 11584 KB Output is correct
3 Correct 2919 ms 20968 KB Output is correct
4 Correct 2391 ms 21160 KB Output is correct
5 Correct 2028 ms 21468 KB Output is correct
6 Correct 1268 ms 20992 KB Output is correct
7 Correct 2905 ms 20928 KB Output is correct
8 Correct 2452 ms 21212 KB Output is correct
9 Correct 2136 ms 21352 KB Output is correct
10 Correct 1311 ms 21016 KB Output is correct
11 Correct 2911 ms 20888 KB Output is correct
12 Correct 12 ms 2772 KB Output is correct
13 Runtime error 218 ms 37092 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -