oj.uz

Submission #897808

# Submission time Handle Problem Language Result Execution time Memory
897808 2024-01-03T17:54:10 Z ShaShi Factories (JOI14_factories) C++17
0 / 100
 83 ms 138424 KB 
#include "factories.h"
#include <bits/stdc++.h>
// #define int long long 
#define F first
#define S second
#define pii pair<int, int>
#define all(x) x.begin(), x.end()
#define kill(x) cout << x << endl, exit(0);
#define mp make_pair
#define pb push_back


using namespace std;
typedef long long ll;

const int MAXN = (int)1e6 + 7;
const int MOD = 998244353;
const int INF = (ll)1e18 + 7;


int n, m, t, k, q, u, v, w, tmp, tmp2, tmp3, tmp4, tmp5, ans2, flag;
ll ans;
int arr[MAXN], sz[MAXN];
bool hate[MAXN];
pair<pair<ll, int>, pair<ll, int> > love[MAXN];
vector<pii> adj[MAXN];
vector<pair<int, ll> > vec[MAXN];


void DFSsz(int v, int p=-1) {
    sz[v] = 1;

    for (auto cur:adj[v]) {
        int u = cur.F;
        if (!hate[u] && u != p) {
            DFSsz(u, v);
            sz[v] += sz[u];
        }
    }
}


int centroid(int tot, int v, int p=-1) {
    for (auto cur:adj[v]) {
        int u = cur.F;

        if (!hate[u] && u != p && 2*sz[u] > tot) return centroid(tot, u, v);
    }

    return v;
}


void all_i_want(int cent, int v, int p, ll dis) {
    for (auto cur:adj[v]) {
        int u = cur.F, w = cur.S;
        if (!hate[u] && u != p) all_i_want(cent, u, v, dis+w);
    }

    vec[v].pb(mp(cent, dis));
}



void solve(int v) {
    DFSsz(v);
    int cent = centroid(sz[v], v);


    hate[cent] = 1;
    for (auto cur:adj[cent]) {
        int u = cur.F, w = cur.S;

        if (!hate[u]) all_i_want(cent, u, cent, w);
    }

    vec[cent].pb(mp(cent, 0ll));

    for (auto cur:adj[cent]) {
        int u = cur.F;
        if (!hate[u]) solve(u);
    }
}


void add(int v, bool x=0) {
    for (auto cur:vec[v]) {
        int u = cur.F;
        ll w = cur.S;

        // cout << "!" << v << " : " << u << " " << w << endl;

        if (x) {
            if (love[u].F.S != flag) {
                love[u].F.S = flag;
                love[u].F.F = w;
            } else {
                love[u].F.F = min(love[u].F.F, w);
            }
        } else {
            if (love[u].S.S != flag) {
                love[u].S.S = flag;
                love[u].S.F = w;
            } else {
                love[u].S.F = min(love[u].S.F, w);
            }
        }

        if (love[u].F.S == love[u].S.S && love[u].S.S == flag) ans = min(ans, love[u].F.F+love[u].S.F);
    }
}



void Init(int N, int A[], int B[], int D[]) {
    n = N;

    for (int i=1; i<n; i++) {
        // cin >> u >> v >> w;
        u = A[i-1], v = B[i-1], w = D[i-1];
        u++, v++;

        adj[u].pb(mp(v, w));
        adj[v].pb(mp(u, w));
    }

    solve(1);
}

long long Query(int S, int X[], int T, int Y[]) {
    cin >> m >> k;
    flag++;

    ans = INF;
    
    while (m--) {
        cin >> u; u++;
        add(u, 0);
    }

    while (k--) {
        cin >> v; v++;
        add(v, 1);
    }
    
    return ans;
}

Compilation message

factories.cpp:18:26: warning: overflow in conversion from 'll' {aka 'long long int'} to 'int' changes value from '1000000000000000007' to '-1486618617' [-Woverflow]
   18 | const int INF = (ll)1e18 + 7;
      |                 ~~~~~~~~~^~~

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 83 ms 138396 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 70 ms 138424 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Runtime error 83 ms 138396 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -