Submission #398107

#	Time	Username	Problem	Language	Result	Execution time	Memory
398107		cpp219	Factories (JOI14_factories)	C++14	Compilation error	0 ms	0 KiB

factories

#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);
}

Compilation message (stderr)

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);
      |                                                     ^~~~
/tmp/ccKM4Yk2.o: In function `main':
grader.cpp:(.text.startup+0x412): undefined reference to `Query(int, int*, int, int*)'
collect2: error: ld returned 1 exit status