oj.uz

답안 #1093880

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1093880 2024-09-27T22:14:56 Z MrPavlito 공장들 (JOI14_factories) C++17
0 / 100
 8000 ms 135764 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<vector<int>> centoidgraf(MAXN);
vector<long long> rez;
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, int 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] ++;
    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, bool foundroot)
{
    int treesize = dfs2(nod, nod);
    int centroid = findCentroid(nod, nod, treesize);
    wasCentoid[centroid] = 1;
    parents[centroid] = p;
    if(!foundroot)
    {
        root = centroid;
        parents[centroid] = centroid;
    }
    else centoidgraf[p].pb(centroid);
    for(auto x:graf[centroid])
    {
        if(wasCentoid[x.fi])continue;
        solve(x.fi, centroid, true);
    }
}

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[]) {
    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]});
    }
    rez = vector<long long>(n, inf);
    dfs(0,0,0);
    fillUp();
    solve(0,0,false);
}

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
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 24156 KB Output is correct
2 Correct 338 ms 42256 KB Output is correct
3 Incorrect 6214 ms 42332 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 24152 KB Output is correct
2 Execution timed out 8077 ms 135764 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 24156 KB Output is correct
2 Correct 338 ms 42256 KB Output is correct
3 Incorrect 6214 ms 42332 KB Output isn't correct
4 Halted 0 ms 0 KB -