Submission #372613

#	Time	Username	Problem	Language	Result	Execution time	Memory
372613		erfanmir	Factories (JOI14_factories)	C++17	Compilation error	0 ms	0 KiB

factories

// In the name of god

//#include "factories.h"
#include <bits/stdc++.h>

using namespace std;

  
typedef long long                   ll;
typedef long double                 ld;
typedef pair<int,int>               pii;
typedef pair<ll,ll>                 pll;
#define all(x)                      (x).begin(),(x).end()
#define lc(x)                       (x) << 1
#define rc(x)                       (x) << 1 | 1
#define F                           first
#define S                           second
#define fast_io                     ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io                     freopen("in.txt" , "r+" , stdin) ; freopen("out.txt" , "w+" , stdout);
#define mp                          make_pair

const int MAXN = 1e6 + 10;
const int MAXLG = 20;
const int MOD = 1e9 + 7;
const int MOD2 = 998244353;
const ll INF = 1e18;

int n, par[MAXN][MAXLG], h[MAXN], st[MAXN], ft[MAXN], cnt, r[MAXN], b[MAXN], stk[MAXN], ptr;
vector<int> g[MAXN];
vector<pii> adj[MAXN];
ll dp[MAXN], rd[MAXN], bd[MAXN];

int A1[MAXN], B1[MAXN], D1[MAXN], X1[MAXN], Y1[MAXN], S1, T1, q;

void dfs(int v = 1){
    st[v] = ++cnt;
    for(auto u : adj[v]){
        if(u.F == par[v][0]){
            continue;
        }
        h[u.F] = h[v] + 1;
        dp[u.F] = dp[v] + u.S;
        par[u.F][0] = v;
        dfs(u.F);
    }
    ft[v] = cnt;
}

int edq(int u, int val){
    for(int i = 0; i < MAXLG; i++){
        if(val & 1){
            u = par[u][i];
        }
        val /= 2;
    }
    return u;
}

int lca(int v, int u){
    if(h[v] > h[u]){
        swap(v, u);
    }
    u = edq(u, h[u] - h[v]);
    if(v == u){
        return v;
    }
    for(int i = MAXLG - 1; ~i; i--){
        if(par[v][i] == par[u][i]){
            continue;
        }
        v = par[v][i];
        u = par[u][i];
    }
    return par[v][0];
}

bool cmp(int A, int B){
    return st[A] < st[B];
}

void Init(int N, int A[], int B[], int D[]){
    n = N;
    for(int i = 0; i < n - 1; i++){
        adj[A[i] + 1].push_back(mp(B[i] + 1, D[i]));
        adj[B[i] + 1].push_back(mp(A[i] + 1, D[i]));
    }
    dfs();
    for(int i = 1; i <= n; i++){
        for(int j = 1; j < MAXLG; j++){
            par[i][j] = par[par[i][j - 1]][j - 1];
        }
    }
}

void sfd(int v){
    rd[v] = bd[v] = INF;
    if(b[v]){
        bd[v] = 0;
    }
    if(r[v]){
        rd[v] = 0;
    }
    for(auto u : g[v]){
        sfd(u);
        bd[v] = min(bd[v], bd[u] - dp[v] + dp[u]);
        rd[v] = min(rd[v], rd[u] - dp[v] + dp[u]);
    }
}

ll Query(int S, int X[], int T, int Y[]){
    ll ans = INF;
    vector<int> vec;

    for(int i = 0; i < S; i++){
        vec.push_back(X[i] + 1);
        b[X[i] + 1] = 1;
    }
    for(int i = 0; i < T; i++){
        vec.push_back(Y[i] + 1);
        r[Y[i] + 1] = 1;
    }
    sort(all(vec), cmp);
    for(int i = 1; i < S + T; i++){
        vec.push_back(lca(vec[i], vec[i - 1]));
    }
    sort(all(vec));
    vec.resize(unique(all(vec)) - vec.begin());

    ptr = 0;
    stk[++ptr] = vec[0];
    for(int i = 1; i < (int)vec.size(); i++){
        while(st[stk[ptr]] > st[vec[i]] || ft[vec[i]] > ft[stk[ptr]]){
            ptr--;
        }
        g[stk[ptr]].push_back(vec[i]);
        stk[++ptr] = vec[i];
    }
    sfd(vec[0]);
    for(auto v : vec){
        g[v].clear();
        ans = min(ans, bd[v] + rd[v]);
        b[v] = r[v] = 0;
    }
    return ans;
}

int main(){
    scanf("%d %d", &n, &q);
    for(int i = 0; i < n - 1; i++){
        scanf("%d %d %d", A1 + i, B1 + i, D1 + i);
    }
    Init(n, A1, B1, D1);
    while(q--){
        scanf("%d %d", &S1, &T1);
        for(int i = 0; i < S1; i++){
            scanf("%d", X1 + i);
        }
        for(int i = 0; i < T1; i++){
            scanf("%d", Y1 +  i);
        }
        printf("%lld\n", Query(S1, X1, T1, Y1));
    }
}

Compilation message (stderr)

factories.cpp: In function 'int main()':
factories.cpp:148:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  148 |     scanf("%d %d", &n, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~
factories.cpp:150:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  150 |         scanf("%d %d %d", A1 + i, B1 + i, D1 + i);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
factories.cpp:154:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  154 |         scanf("%d %d", &S1, &T1);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~
factories.cpp:156:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  156 |             scanf("%d", X1 + i);
      |             ~~~~~^~~~~~~~~~~~~~
factories.cpp:159:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  159 |             scanf("%d", Y1 +  i);
      |             ~~~~~^~~~~~~~~~~~~~~
/tmp/cclrXZa0.o: In function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/ccUMmE07.o:factories.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status