oj.uz

답안 #878599

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
878599 2023-11-24T21:52:55 Z cpptowin 공장들 (JOI14_factories) C++17
0 / 100
 8000 ms 160208 KB 
#include"factories.h"
#include<bits/stdc++.h>
#define fo(i,d,c) for(int i=d;i<=c;i++)
#define fod(i,c,d) for(int i=c;i>=d;i--)
#define maxn 1000010
#define fi first
#define se second
#define pb emplace_back
#define inf 1000000000
#define pii pair<int,int>
#define vii vector<pii>
#define vi vector<int>
using namespace std;
vii ke[maxn];
int par[maxn][20],sz[maxn];
long long d[maxn];
int ind[maxn],head[maxn],cnt = 1;
int minn[maxn][20];
vector<array<int,4>> adj;
void dfs(int u,int parent)
{
    sz[u] = 1;
    for(auto [v,w] : ke[u])
    {
        if(v == parent) continue;
        par[v][0] = u;
        d[v] = d[u] + w;
        dfs(v,u);
        sz[u] += sz[v];
    }
}
void hld(int u,int parent)
{
    if(head[cnt] == 0) head[cnt] = u;
    ind[u] = cnt;
    int  sc = -1,maxx = -1;
    for(auto [v,w] : ke[u]) if(v != parent)
        {
            if(maxx < sz[v])
            {
                maxx = sz[v];
                sc = v;
            }
        }
    if(sc != -1) hld(sc,u);
    for(auto [v,w] : ke[u]) if(v != parent and v != sc)
        {
            cnt++;
            hld(v,u);
        }
}
void get(int u,int t)
{
    long long val = d[u];
    int uchain,vchain = ind[1];
    while(1)
    {
        uchain = ind[u];
        adj.push_back({uchain,u,val,t});
        if(uchain == vchain) return;
        u = ind[u];
        u = par[head[u]][0];
    }
}
void Init(int N,int A[],int B[],int D[])
{
    fo(i,0,N - 2)
    {
        ke[A[i] + 1].pb(B[i] + 1,D[i]);
        ke[B[i] + 1].pb(A[i] + 1,D[i]);
    }
    dfs(1,1);
    hld(1,1);
}
long long Query(int S, int X[], int T, int Y[])
{
    long long ans = 2e18;
    fo(i,0,S - 1) get(X[i] + 1,0);
    fo(i,0,T - 1) get(Y[i] + 1,1);
    sort(adj.begin(),adj.end(),[](array<int,4> a,array<int,4> b)
    {
        return d[a[1]] > d[b[1]];
    });
    fo(i,1,cnt) fo(j,0,1) minn[i][j] = 2e18;
    for(auto [p,v,dist,t] : adj)
    {
        ans = min(ans,minn[p][1 - t] - 2 * d[v] + dist);
        minn[p][t] = min(minn[p][t],dist);
    }
    adj.clear();
    return ans;
}

Compilation message

factories.cpp: In function 'void get(int, int)':
factories.cpp:59:33: warning: narrowing conversion of 'val' from 'long long int' to 'int' [-Wnarrowing]
   59 |         adj.push_back({uchain,u,val,t});
      |                                 ^~~
factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:84:40: warning: overflow in conversion from 'double' to 'int' changes value from '2.0e+18' to '2147483647' [-Woverflow]
   84 |     fo(i,1,cnt) fo(j,0,1) minn[i][j] = 2e18;
      |                                        ^~~~

Subtask #1
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 49756 KB Output is correct
2 Incorrect 670 ms 66028 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 49764 KB Output is correct
2 Execution timed out 8067 ms 160208 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 49756 KB Output is correct
2 Incorrect 670 ms 66028 KB Output isn't correct
3 Halted 0 ms 0 KB -