Submission #1088210

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

factories

//Dost SEFEROĞLU
//Lazy Persistent Dynamic 3D Segment Tree (feat. Selo) 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define ff first
#define ss second
#define sp << " " <<    
#define all(cont) cont.begin(),cont.end()
#define vi vector<int>
const int MOD = 1e9+7,inf = 2e14;
const int N = 5e5+50;
int timer = 1;
vector<pii> edges[N];
int up[N][20],d[N],tin[N],tout[N],c[N],red[N],blue[N];

void dfs(int node,int p,int dep = 0) {
    tin[node] = timer++;
    d[node] = dep;
    up[node][0] = p;
    for (auto it : edges[node]) {
        if (it.ff == p) continue;
        dfs(it.ff,node,dep+it.ss);
    }
    tout[node] = timer-1;
}

bool anc(int a,int b) {
    return tin[a] <= tin[b] && tout[a] >= tout[b];
} 

int lca(int a,int b) {
    if (anc(a,b)) return a;
    if (anc(b,a)) return b;
    for (int i=19;i>=0;i--) {
        if (!anc(up[a][i],b)) a = up[a][i];
    }
    return up[a][0];
}
vi edg[N];

int solver(int node) {
    red[node] = blue[node] = inf;
    if (c[node] == 1) red[node] = d[node];
    if (c[node] == 2) blue[node] = d[node];
    int ans = inf;
    for (auto it : edg[node]) {
        ans = min(ans,solver(it));
        red[node] = min(red[node],red[it]);
        blue[node] = min(blue[node],blue[it]);
    }
    //cout << node sp red[node] sp blue[node] sp d[node]<< endl;
    ans = min(ans,red[node]+blue[node]-2*d[node]);
    return ans;
}

void solve() {
    int n,q;
    cin >> n >> q;
    for (int i=1;i<=n-1;i++) {
        int a,b,c;
        cin >> a >> b >> c;
        edges[a].push_back({b,c});
        edges[b].push_back({a,c});
    }
    dfs(0,0);
    for (int i=1;i<20;i++) {
        for (int j=0;j<n;j++) up[j][i] = up[up[j][i-1]][i-1];
    }
    while (q--) {
        int s,t;
        cin >> s >> t;
        vector<int> nodes;
        vi x(s),y(t);
        for (int i=0;i<s;i++) {
            cin >> x[i];
            c[x[i]] = 1;
            nodes.push_back(x[i]);
        }
        for (int i=0;i<t;i++) {
            cin >> y[i];
            c[y[i]] = 2;
            nodes.push_back(y[i]);
        }
        sort(all(nodes),[&](int n1,int n2) {
            return tin[n1] < tin[n2];
        });
        for (int i=0;i<s+t;i++) {
            nodes.push_back(lca(nodes[i],nodes[(i+1)%nodes.size()]));
        }
        sort(all(nodes),[&](int n1,int n2) {
            return tin[n1] < tin[n2];
        });
        nodes.erase(unique(all(nodes)),nodes.end()); 
        stack<int> st;
        st.push(nodes[0]);
        for (int i=1;i<nodes.size();i++) {
            while (!anc(st.top(),nodes[i])) {
                st.pop();
            }
            edg[st.top()].push_back(nodes[i]);
            st.push(nodes[i]);
        }
        int ans = solver(nodes[0]);
        cout << ans << endl;
        for (auto it : nodes) edg[it].clear(),c[it] = 0;
    }
}                    
                             
signed main() { 
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    #ifdef Dodi
        freopen("in.txt","r",stdin);
        freopen("out.txt","w",stdout);
    #endif
    int t = 1;
    //cin >> t; 
    while (t --> 0) solve();
}

Compilation message (stderr)

factories.cpp: In function 'void solve()':
factories.cpp:98:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |         for (int i=1;i<nodes.size();i++) {
      |                      ~^~~~~~~~~~~~~
/usr/bin/ld: /tmp/ccROqfX2.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccRstSh4.o:factories.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccROqfX2.o: in function `main':
grader.cpp:(.text.startup+0x37d): undefined reference to `Init(int, int*, int*, int*)'
/usr/bin/ld: grader.cpp:(.text.startup+0x412): undefined reference to `Query(int, int*, int, int*)'
collect2: error: ld returned 1 exit status