oj.uz

Submission #473016

# Submission time Handle Problem Language Result Execution time Memory
473016 2021-09-14T18:12:45 Z ljuba Factories (JOI14_factories) C++17
15 / 100
 8000 ms 407320 KB 
#include "factories.h"
#include <bits/stdc++.h>

using namespace std;

const int mxN = 5e5 + 12;

typedef long long ll;

vector<pair<int, ll>> adj[mxN];
bool vis[mxN];
int sub[mxN];

//plasim se da ce biti sporo :/

int dfsSize(int s, int p = -1) {
    sub[s] = 1;
    for(auto b : adj[s]) {
        int e = b.first;
        if(e == p || vis[e])
            continue;
        dfsSize(e, s);
        sub[s] += sub[e];
    }
    return sub[s];
}

int centroid(int s, int p, int n) {
    for(auto b : adj[s]) {
        int e = b.first;
        if(e == p || vis[e])
            continue;

        if(2*sub[e] > n)
            return centroid(e, s, n);
    }

    return s;
}

map<int, ll> dist[mxN];

void dfs(int s, int p, int c) {
    ll vrednost = -1;
    for(auto b : adj[s]) {
        int e = b.first;
        if(e == p) {
            vrednost = b.second;
            break;
        }
    }
    if(vrednost == -1) {
        dist[c][s] = 0;
    } else {
        dist[c][s] = dist[c][p] + vrednost;
    }
    for(auto b : adj[s]) {
        int e = b.first;
        if(e == p || vis[e])
            continue;
        dfs(e, s, c);
    }
}

int iznad[mxN];

void build(int s, int p = -1) {
    int n = dfsSize(s);
    int c = centroid(s, -1, n);

    dfs(c, -1, c);
    iznad[c] = p;
    vis[c] = true;

    for(auto b : adj[c]) {
        int e = b.first;
        if(vis[e])
            continue;
        build(e, c);
    }
}

ll mini[mxN];

void Init(int N, int A[], int B[], int D[]) {
    for(int i = 0; i < N-1; ++i) {
        int u = A[i], v = B[i];
        ll w = D[i];
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }

    build(0);

    //for(int i = 0; i < N; ++i) {
        //vector<pair<int, ll>> temp;
        //for(auto z : dist[i]) {
            //temp.push_back(z);
        //}
        //cout << i << ":";
        //for(auto z : temp)
            //cout << " {" << z.first << ", " << z.second << "}";
        //cout << endl;
    //}

    for(int i = 0; i < N; ++i)
        mini[i] = LLONG_MAX;
}

long long Query(int S, int X[], int T, int Y[]) {
    //drzi za prve, za druge samo proveri
    ll ans = LLONG_MAX;
    for(int i = 0; i < S; ++i) {
        int trenutni = X[i];
        int iteriraj = trenutni;
        while(iteriraj != -1) {
            mini[iteriraj] = min(mini[iteriraj], dist[iteriraj][trenutni]);
            iteriraj = iznad[iteriraj];
        }
    }

    for(int i = 0; i < T; ++i) {
        int trenutni = Y[i];
        int iteriraj = trenutni;
        while(iteriraj != -1) {
            if(mini[iteriraj] != LLONG_MAX) {
                ans = min(ans, mini[iteriraj] + dist[iteriraj][trenutni]);
            }
            iteriraj = iznad[iteriraj];
        }
    }

    for(int i = 0; i < S; ++i) {
        int iteriraj = X[i];
        while(iteriraj != -1) {
            mini[iteriraj] = LLONG_MAX;
            iteriraj = iznad[iteriraj];
        }
    }

    return ans;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 35916 KB Output is correct
2 Correct 1622 ms 45992 KB Output is correct
3 Correct 2463 ms 47012 KB Output is correct
4 Correct 1841 ms 47000 KB Output is correct
5 Correct 2950 ms 47764 KB Output is correct
6 Correct 494 ms 44600 KB Output is correct
7 Correct 2415 ms 46868 KB Output is correct
8 Correct 2455 ms 47080 KB Output is correct
9 Correct 2968 ms 47884 KB Output is correct
10 Correct 495 ms 44580 KB Output is correct
11 Correct 2406 ms 47028 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 35788 KB Output is correct
2 Execution timed out 8066 ms 407320 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 35916 KB Output is correct
2 Correct 1622 ms 45992 KB Output is correct
3 Correct 2463 ms 47012 KB Output is correct
4 Correct 1841 ms 47000 KB Output is correct
5 Correct 2950 ms 47764 KB Output is correct
6 Correct 494 ms 44600 KB Output is correct
7 Correct 2415 ms 46868 KB Output is correct
8 Correct 2455 ms 47080 KB Output is correct
9 Correct 2968 ms 47884 KB Output is correct
10 Correct 495 ms 44580 KB Output is correct
11 Correct 2406 ms 47028 KB Output is correct
12 Correct 22 ms 35788 KB Output is correct
13 Execution timed out 8066 ms 407320 KB Time limit exceeded
14 Halted 0 ms 0 KB -