Submission #780066

#	Time	Username	Problem	Language	Result	Execution time	Memory
780066		khanhphucscratch	Factories (JOI14_factories)	C++14	0 / 100	1509 ms	216680 KiB

factories

#include<bits/stdc++.h>
#include "factories.h"
using namespace std;
vector<int> ad[500001], c[500001], ad2[500001], c2[500001];
int n, type[500001], tin[500001], tout[500001], sparse[20][1000002], h[500001], dis[500001], lg2[1000003], appear[500001], ganl[500001], ganr[500001], dfsc = 0, cur = 0;
bool visited[500001];
void dfs(int u)
{
    tin[u] = ++dfsc;
    visited[u] = 1;
    sparse[0][++cur] = u;
    appear[u] = cur;
    for(int i = 0; i < ad[u].size(); i++) if(visited[ad[u][i]] == 0){
        int v = ad[u][i];
        h[v] = h[u] + 1;
        dis[v] = dis[u] + c[u][i];
        dfs(v);
        sparse[0][++cur] = u;
    }
    tout[u] = dfsc;
}
void preprocess()
{
    for(int i = 1; i < 20; i++){
        for(int j = 1; j + (1 << (i-1)) <= cur; j++){
            int k = j + (1 << (i-1));
            if(h[sparse[i-1][j]] < h[sparse[i-1][k]]) sparse[i][j] = sparse[i-1][j];
            else sparse[i][j] = sparse[i-1][k];
            //cout<<i<<" "<<j<<" "<<sparse[i][j]<<endl;
        }
    }
}
int lca(int u, int v)
{
    int l = appear[u], r = appear[v];
    if(l > r) swap(l, r);
    int x = lg2[r-l+1];
    if(h[sparse[x][l]] < h[sparse[x][r-(1 << x)+1]]) return sparse[x][l];
    else return sparse[x][r-(1 << x)+1];
}
bool cmp(int u, int v)
{
    return tin[u] < tin[v];
}
bool ancestor(int u, int v)
{
    return (tin[u] <= tin[v] && tout[u] >= tout[v]);
}
void Init(int N, int a[], int b[], int d[])
{
    n = N;
    for(int i = 0; i < n; i++){a[i]++; b[i]++;}
    for(int i = 0; i < n-1; i++){
        ad[a[i]].push_back(b[i]);
        ad[b[i]].push_back(a[i]);
        c[a[i]].push_back(d[i]);
        c[b[i]].push_back(d[i]);
    }
    h[0] = 1e9;
    dfs(1);
    preprocess();
    for(int i = 2; i <= 2*n; i++){
        if((1 << lg2[i-1])*2 > i) lg2[i] = lg2[i-1];
        else lg2[i] = lg2[i-1]+1;
    }
    for(int i = 1; i <= n; i++){
        visited[i] = 0; ganl[i] = 1e9; ganr[i] = 1e9;
    }
}
void dfsdp(int u)
{
    visited[u] = 1;
    ganl[u] = 1e9; ganr[u] = 1e9;
    if(type[u] == 1) ganl[u] = 0;
    if(type[u] == 2) ganr[u] = 0;
    for(int i = 0; i < ad2[u].size(); i++) if(visited[ad2[u][i]] == 0){
        int v = ad2[u][i];
        dfsdp(v);
        ganl[u] = min(ganl[u], ganl[v] + c2[u][i]);
        ganr[u] = min(ganr[u], ganr[v] + c2[u][i]);
    }
    visited[u] = 0;
}
void dfsreroot(int u, int par, int cost)
{
    if(par > 0){
        ganl[u] = min(ganl[u], ganl[par] + cost);
        ganr[u] = min(ganr[u], ganr[par] + cost);
    }
    for(int i = 0; i < ad2[u].size(); i++) if(ad2[u][i] != par){
        int v = ad2[u][i];
        dfsreroot(v, u, c2[u][i]);
    }
}
long long Query(int s, int x[], int t, int y[])
{
    vector<int> st; //build virtual tree
    for(int i = 0; i < s; i++){
        x[i]++;
        st.push_back(x[i]);
        type[x[i]] = 1;
    }
    for(int i = 0; i < t; i++){
        y[i]++;
        st.push_back(y[i]);
        type[y[i]] = 2;
    }
    sort(st.begin(), st.end(), cmp);
    for(int i = 0; i < s+t-1; i++){
        int node = lca(st[i], st[i+1]);
        if(node != st[i] && node != st[i+1]) st.push_back(node);
    }
    sort(st.begin(), st.end(), cmp);
    stack<int> wtf;
    int bruh = 0;
    for(int u : st){
        while(wtf.size() > 0 && ancestor(wtf.top(), u) == 0) wtf.pop();
        if(wtf.size() > 0){
            ad2[u].push_back(wtf.top());
            ad2[wtf.top()].push_back(u);
            c2[u].push_back(dis[u] - dis[wtf.top()]);
            c2[wtf.top()].push_back(dis[u] - dis[wtf.top()]);
            bruh++;
        }
        wtf.push(u);
    }
    int root = st[0];
    dfsdp(root);
    long long ans = 1e9;
    for(int u : st){
        ans = min(ans, (long long)ganl[u] + ganr[u]);
        type[u] = 0; ad2[u].clear(); c2[u].clear(); ganl[u] = 1e9; ganr[u] = 1e9;
    }
    return ans;
}
/*int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n, q;
    cin>>n>>q;
    int u[n-1], v[n-1], cost[n-1];
    for(int i = 0; i < n-1; i++) cin>>u[i]>>v[i]>>cost[i];
    Init(n, u, v, cost);
    for(int test = 0; test < q; test++){
        int a, b;
        cin>>a>>b;
        int l[a], r[b];
        for(int i = 0; i < a; i++) cin>>l[i];
        for(int i = 0; i < b; i++) cin>>r[i];
        cout<<Query(a, l, b, r)<<'\n';
    }
}
*/

Compilation message (stderr)

factories.cpp: In function 'void dfs(int)':
factories.cpp:13:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 |     for(int i = 0; i < ad[u].size(); i++) if(visited[ad[u][i]] == 0){
      |                    ~~^~~~~~~~~~~~~~
factories.cpp: In function 'void dfsdp(int)':
factories.cpp:76:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |     for(int i = 0; i < ad2[u].size(); i++) if(visited[ad2[u][i]] == 0){
      |                    ~~^~~~~~~~~~~~~~~
factories.cpp: In function 'void dfsreroot(int, int, int)':
factories.cpp:90:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |     for(int i = 0; i < ad2[u].size(); i++) if(ad2[u][i] != par){
      |                    ~~^~~~~~~~~~~~~~~

• Subtask 1: 0 / 15
• Subtask 2: 0 / 18
• Subtask 3: 0 / 67