oj.uz

Submission #1093884

# Submission time Handle Problem Language Result Execution time Memory
1093884 2024-09-27T22:31:40 Z MrPavlito Factories (JOI14_factories) C++17
15 / 100
 8000 ms 115868 KB 
#include "factories.h"
#include <bits/stdc++.h>
//#define int long long
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define sc second
#define endl "\n"
#define pii pair<int,int>

using namespace std;

const int MAXN = 5e5+5;
const int mod7 = 1e9+7;
const long long inf = 1e15;
const int lg = 20;
int t = 1;

vector<vector<pii>> graf(MAXN);
vector<long long> rez(MAXN, inf);
int subtreesize[MAXN];
long long dist[MAXN];
int tin[MAXN];
int tout[MAXN];
int parents[MAXN];
int up[MAXN][lg];
bool wasCentoid[MAXN];
int root;
int n,q;

void dfs(int nod, int p, long long d)
{
    dist[nod] = d;
    tin[nod] = t++;
    up[nod][0] = p;
    for(auto x: graf[nod])if(x.fi != p)dfs(x.fi, nod, d+x.sc);
    tout[nod] = t++;
}

void fillUp()
{
    for(int i=1; i<lg; i++)
    {
        for(int j=0; j<n; j++)
        {
            up[j][i] = up[up[j][i-1]][i-1];
        }
    }
}

int lca(int u, int v)
{
    if(u==v)return u;
    if(tin[u] < tin[v] && tout[u] > tout[v])return u;
    if(tin[u] > tin[v] && tout[u] < tout[v])return v;
    for(int i=lg-1; i>=0; i--)
    {
        int guess = up[v][i];
        if(!(tin[u] > tin[guess] && tout[u] < tout[guess]))v = guess;
    }
    return up[v][0];
}

int dfs2(int nod, int p)
{
    subtreesize[nod] = 1;
    for(auto x: graf[nod])
    {
        if(x.fi == p || wasCentoid[x.fi])continue;
        subtreesize[nod] += dfs2(x.fi, nod);
    }
    return subtreesize[nod];
}

int findCentroid(int nod, int p, int treesize)
{
    for(auto x: graf[nod])
    {
        if(x.fi==p || wasCentoid[x.fi])continue;
        if(subtreesize[x.fi] * 2 > treesize)return findCentroid(x.fi, nod, treesize);
    }
    return nod;
}

void solve(int nod, int p)
{
    int treesize = dfs2(nod, nod);
    int centroid = findCentroid(nod, nod, treesize);
    wasCentoid[centroid] = 1;
    parents[centroid] = p;
    if(p == -1)
    {
        root = centroid;
        parents[centroid] = centroid;
    }
    for(auto x:graf[centroid])
    {
        if(wasCentoid[x.fi])continue;
        solve(x.fi, centroid);
    }
}

long long findDist(int u, int v)
{
    return dist[u] + dist[v] - 2*dist[lca(u,v)];
}

void update(int nod)
{
     int trnod = nod;
     while(trnod != parents[trnod])
     {
        rez[trnod] = min(rez[trnod],findDist(nod, trnod));
        trnod = parents[trnod];
     }
     rez[trnod] = min(rez[trnod], findDist(nod, trnod));
}

long long query(int nod)
{
    int trnod = nod;
    long long trrez= inf;
    while(trnod != parents[trnod])
     {
        trrez = min(trrez, rez[trnod] + findDist(nod, trnod));
        trnod = parents[trnod];
     }
     trrez = min(trrez, rez[trnod] + findDist(nod, trnod));
     return trrez;
}

/*
signed main()
{
    ios_base::sync_with_stdio(false),cin.tie(0), cout.tie(0);
    int tt=1;
    //cin >> tt;
    while(tt--)
    {

        cin >> n >> q;
        rez = vector<long long>(n, inf);
        for(int i=0; i<n-1; i++)
        {
            int a,b,w;cin >> a >> b >> w;
            graf[a].pb({b,w});
            graf[b].pb({a,w});
        }
        dfs(0,0,0);
        fillUp();
        solve(0,0,false);
        //for(int i=0; i<n; i++)cout << parents[i] << " ";cout << endl;
        while(q--)
        {
            int a,b;cin >> a >> b;
            vector<int> factory1(a);
            for(int i=0; i<a; i++)
            {
                cin >> factory1[i];
                update(factory1[i]);
            }
            vector<int> factory2(b);
            int finalrez = inf;
            for(int i=0; i<b; i++)
            {
                cin >> factory2[i];
                finalrez = min(finalrez, query(factory2[i]));
            }

            ///reset cenmtorid tree
            for(int i=0; i<n; i++)
            {
                int nod = i;
                while(rez[nod] !=inf)
                {
                    rez[nod] = inf;
                    nod = parents[nod];
                }
            }

            cout << finalrez << endl;
        }


    }
}
*/

void Init(int N, int A[], int B[], int D[]) {
    ios_base::sync_with_stdio(false);cin.tie(0);
    n = N;
    for(int i=0; i<n-1; i++)
    {
        graf[A[i]].pb({B[i],D[i]});
        graf[B[i]].pb({A[i],D[i]});
    }
    dfs(0,0,0);
    fillUp();
    solve(0,-1);
}

long long Query(int S, int X[], int T, int Y[]) {
  for(int i=0; i<S; i++)update(X[i]);

   long long finalrez = inf;
    for(int i=0; i<T; i++)finalrez = min(finalrez, query(Y[i]));
    for(int i=0; i<n; i++)
    {
        int nod = i;
        while(rez[nod] !=inf)
        {
            rez[nod] = inf;
            nod = parents[nod];
        }
    }
    return finalrez;

}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 16472 KB Output is correct
2 Correct 431 ms 34204 KB Output is correct
3 Correct 841 ms 34180 KB Output is correct
4 Correct 769 ms 34384 KB Output is correct
5 Correct 406 ms 34388 KB Output is correct
6 Correct 180 ms 34200 KB Output is correct
7 Correct 790 ms 34376 KB Output is correct
8 Correct 851 ms 34384 KB Output is correct
9 Correct 410 ms 34392 KB Output is correct
10 Correct 181 ms 34392 KB Output is correct
11 Correct 801 ms 34396 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 16224 KB Output is correct
2 Execution timed out 8063 ms 115868 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 16472 KB Output is correct
2 Correct 431 ms 34204 KB Output is correct
3 Correct 841 ms 34180 KB Output is correct
4 Correct 769 ms 34384 KB Output is correct
5 Correct 406 ms 34388 KB Output is correct
6 Correct 180 ms 34200 KB Output is correct
7 Correct 790 ms 34376 KB Output is correct
8 Correct 851 ms 34384 KB Output is correct
9 Correct 410 ms 34392 KB Output is correct
10 Correct 181 ms 34392 KB Output is correct
11 Correct 801 ms 34396 KB Output is correct
12 Correct 8 ms 16224 KB Output is correct
13 Execution timed out 8063 ms 115868 KB Time limit exceeded
14 Halted 0 ms 0 KB -