oj.uz

Submission #398265

# Submission time Handle Problem Language Result Execution time Memory
398265 2021-05-04T03:55:11 Z cpp219 Factories (JOI14_factories) C++14
100 / 100
 4874 ms 110844 KB 
#pragma GCC optimization "O2"
#pragma GCC optimization "unroll-loop"
#pragma GCC target ("avx2")
#include "factories.h"
#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define fs first
#define sc second
using namespace std;
typedef pair<ll,ll> LL;
const ll N = 5e5 + 9;
const ll inf = 1e16 + 7;
vector<LL> g[N];
ll n,chainHead[N],curChain[N],posIn[N],now = 1,cnt = 1,child[N],dep[N],par[N];
ll suf[2][N],ans;
void DFS(ll u,ll p){
    child[u] = 1; par[u] = p; //cout<<par[0]<<"x\n"; //exit(0);
    //cout<<u<<" x "<<p<<"\n";
    for (auto i : g[u]){
        ll v = i.fs;
        if (v != p) dep[v] = dep[u] + i.sc,DFS(v,u),child[u] += child[v];
    }
}

void DFS_hld(ll u,ll p){
    curChain[u] = now;
    if (chainHead[now] == -1) chainHead[now] = u;
    ll chosen = -1,mx = 0;
    for (auto i : g[u]){
        ll v = i.fs;
        if (v != p&&child[v] > mx) mx = child[v],chosen = v;
    }
    if (chosen >= 0) DFS_hld(chosen,u);
    for (auto i : g[u]){
        ll v = i.fs;
        if (v != p&&v != chosen) now++,DFS_hld(v,u);
    }
}

void Init(int sz,int A[],int B[],int D[]){
    memset(chainHead,-1,sizeof(chainHead));
    for (ll i = 0;i < sz - 1;i++){
        ll x = A[i],y = B[i],w = D[i];
        g[x].push_back({y,w}); g[y].push_back({x,w});
    }
    DFS(0,-1); DFS_hld(0,-1);
}

struct Node{
    ll path,Lnode,d,type;
};

vector<Node> v;
/// suffix min

void To_root(ll now,ll d,ll type){
    while(now >= 0){
        ll path = curChain[now],nxt = par[chainHead[path]];
        //cout<<now<<" "<<par[3]; exit(0);
        v.push_back({path,now,d,type}); now = nxt;
    }
    //exit(0);
}

bool lf1(Node a,Node b){
    return a.path < b.path;
}

bool lf2(Node a,Node b){
    return dep[a.Lnode] < dep[b.Lnode] || (dep[a.Lnode] == dep[b.Lnode] && a.type < b.type);
}

void calSuf(ll L,ll R){
    vector<Node> have;
    for (ll i = L;i <= R;i++) have.push_back(v[i]); sort(have.begin(),have.end(),lf2);
    suf[0][have.size()] = suf[1][have.size()] = inf;
    for (ll i = have.size() - 1;i >= 0;i--){
        suf[0][i] = suf[0][i + 1]; suf[1][i] = suf[1][i + 1];
        ll cur = have[i].type;
        suf[cur][i] = min(suf[cur][i],have[i].d);
    }
    //cout<<suf[0][1]; exit(0);
    for (ll i = have.size() - 1;i >= 0;i--){
        ll cur = have[i].type;
        ans = min(ans,have[i].d + suf[1 - cur][i + 1] - 2*dep[have[i].Lnode]);
        //cout<<have[i].d <<" "<< suf[1 - cur][i + 1] <<" "<< 2*dep[have[i].Lnode]<<"x\n";
    }
    //exit(0);
}

ll Query(int S,int X[],int T,int Y[]){
    v.clear(); ans = inf;
    for (ll i = 0;i < S;i++) To_root(X[i],dep[X[i]],0);
    for (ll i = 0;i < T;i++) To_root(Y[i],dep[Y[i]],1);
    sort(v.begin(),v.end(),lf1); ll sz = v.size();
    //for (auto i : v) cout<<i.path<<" "<<i.Lnode<<" "<<i.d<<" "<<i.type<<"\n"; cout<<"\n";
    //exit(0);
    for (ll i = 0;i < sz;i){
        ll j = i + 1;
        while(j < sz&&v[j].path == v[i].path) j++;
        //cout<<i<<" "<<j - 1; exit(0);
        calSuf(i,j - 1); i = j;
        //cout<<v[i].d<<" "<<suf[i + 1]<<" "<<dep[v[i].Lnode]<<"\n";
    }
    return ans;
}

Compilation message

factories.cpp:1: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    1 | #pragma GCC optimization "O2"
      | 
factories.cpp:2: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    2 | #pragma GCC optimization "unroll-loop"
      | 
factories.cpp: In function 'void calSuf(long long int, long long int)':
factories.cpp:76:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   76 |     for (ll i = L;i <= R;i++) have.push_back(v[i]); sort(have.begin(),have.end(),lf2);
      |     ^~~
factories.cpp:76:53: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   76 |     for (ll i = L;i <= R;i++) have.push_back(v[i]); sort(have.begin(),have.end(),lf2);
      |                                                     ^~~~
factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:99:26: warning: for increment expression has no effect [-Wunused-value]
   99 |     for (ll i = 0;i < sz;i){
      |                          ^

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 16472 KB Output is correct
2 Correct 1859 ms 26172 KB Output is correct
3 Correct 1394 ms 25760 KB Output is correct
4 Correct 1522 ms 26508 KB Output is correct
5 Correct 806 ms 26364 KB Output is correct
6 Correct 1026 ms 26108 KB Output is correct
7 Correct 1342 ms 25720 KB Output is correct
8 Correct 1389 ms 26440 KB Output is correct
9 Correct 783 ms 26368 KB Output is correct
10 Correct 1030 ms 26148 KB Output is correct
11 Correct 1340 ms 25636 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 16112 KB Output is correct
2 Correct 2274 ms 83208 KB Output is correct
3 Correct 1411 ms 73324 KB Output is correct
4 Correct 988 ms 73220 KB Output is correct
5 Correct 1127 ms 110844 KB Output is correct
6 Correct 1580 ms 88456 KB Output is correct
7 Correct 1220 ms 46872 KB Output is correct
8 Correct 888 ms 46744 KB Output is correct
9 Correct 800 ms 50800 KB Output is correct
10 Correct 1233 ms 48148 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 16472 KB Output is correct
2 Correct 1859 ms 26172 KB Output is correct
3 Correct 1394 ms 25760 KB Output is correct
4 Correct 1522 ms 26508 KB Output is correct
5 Correct 806 ms 26364 KB Output is correct
6 Correct 1026 ms 26108 KB Output is correct
7 Correct 1342 ms 25720 KB Output is correct
8 Correct 1389 ms 26440 KB Output is correct
9 Correct 783 ms 26368 KB Output is correct
10 Correct 1030 ms 26148 KB Output is correct
11 Correct 1340 ms 25636 KB Output is correct
12 Correct 13 ms 16112 KB Output is correct
13 Correct 2274 ms 83208 KB Output is correct
14 Correct 1411 ms 73324 KB Output is correct
15 Correct 988 ms 73220 KB Output is correct
16 Correct 1127 ms 110844 KB Output is correct
17 Correct 1580 ms 88456 KB Output is correct
18 Correct 1220 ms 46872 KB Output is correct
19 Correct 888 ms 46744 KB Output is correct
20 Correct 800 ms 50800 KB Output is correct
21 Correct 1233 ms 48148 KB Output is correct
22 Correct 4874 ms 96420 KB Output is correct
23 Correct 4149 ms 100264 KB Output is correct
24 Correct 3157 ms 93560 KB Output is correct
25 Correct 2886 ms 94708 KB Output is correct
26 Correct 2601 ms 78276 KB Output is correct
27 Correct 2078 ms 107984 KB Output is correct
28 Correct 2000 ms 85108 KB Output is correct
29 Correct 2480 ms 75288 KB Output is correct
30 Correct 2536 ms 74844 KB Output is correct
31 Correct 2426 ms 75488 KB Output is correct
32 Correct 1314 ms 50060 KB Output is correct
33 Correct 1411 ms 47740 KB Output is correct
34 Correct 2695 ms 33984 KB Output is correct
35 Correct 2656 ms 33988 KB Output is correct
36 Correct 1618 ms 34420 KB Output is correct
37 Correct 1582 ms 34356 KB Output is correct