Submission #927583

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

factories

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int Nmax=500010, INF=1e18;
int mx;
int N, Q, sz[Nmax], par[Nmax], lv[Nmax], dep[20][Nmax], num[Nmax];
bool chk[Nmax];
vector<pair<int, int>> adj[Nmax];
int px[Nmax], py[Nmax];
vector<int> X[Nmax], Y[Nmax];

int DFS_S(int curr, int prev) {
    sz[curr]=1;
    for(auto [next, w]:adj[curr]) if(next!=prev && !chk[next]) sz[curr]+=DFS_S(next, curr);
    return sz[curr];
}

int DFS_C(int curr, int prev, int s) {
    for(auto [next, w]:adj[curr]) if(next!=prev && !chk[next] && sz[next]>=s/2) return DFS_C(next, curr, s);
    return curr;
}

void DFS_D(int curr, int prev, int lev) {
    for(auto [next, w]:adj[curr]) if(next!=prev && !chk[next]) {
        dep[lev][next]=dep[lev][curr]+w;
        DFS_D(next, curr, lev);
    }
}

int DnC(int curr, int lev) {
    mx=max(mx, lev);
    int s=DFS_S(curr, 0), C=DFS_C(curr, 0, s);
    chk[C]=true, lv[C]=lev;
    DFS_D(C, 0, lev);
    for(auto [next, w]:adj[C]) if(!chk[next]) par[DnC(next, lev+1)]=C;
    return C;
}

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>N>>Q;
    for(int i=1; i<N; i++) {
        int u, v, w; cin>>u>>v>>w;
        u++, v++;
        adj[u].push_back({v, w}), adj[v].push_back({u, w});
    }
    DnC(1, 0);
    fill(num+1, num+N+1, -1);
    while(Q--) {
        int a, b; cin>>a>>b;
        vector<int> V;
        for(int i=1; i<=a; i++) {
            int x; cin>>x; x++;
            for(int p=x; p; p=par[p]) {
                X[p].push_back(dep[lv[p]][x]);
                if(num[p]!=Q) V.push_back(p), num[p]=Q;
            }
        }
        for(int i=1; i<=b; i++) {
            int x; cin>>x; x++;
            for(int p=x; p; p=par[p]) {
                Y[p].push_back(dep[lv[p]][x]);
                if(num[p]!=Q) V.push_back(p), num[p]=Q;
            }
        }
        int ret=INF;
        for(int x:V) {
            int ma=INF, mb=INF;
            for(int i=px[x]; i<X[x].size(); i++) ma=min(ma, X[x][i]);
            for(int i=py[x]; i<Y[x].size(); i++) mb=min(mb, Y[x][i]);
            ret=min(ret, ma+mb);
            px[x]=X[x].size(), py[x]=Y[x].size();
        }
        cout<<ret<<"\n";
    }
    return 0;
}

Compilation message (stderr)

factories.cpp: In function 'int main()':
factories.cpp:70:31: 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]
   70 |             for(int i=px[x]; i<X[x].size(); i++) ma=min(ma, X[x][i]);
      |                              ~^~~~~~~~~~~~
factories.cpp:71:31: 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]
   71 |             for(int i=py[x]; i<Y[x].size(); i++) mb=min(mb, Y[x][i]);
      |                              ~^~~~~~~~~~~~
/usr/bin/ld: /tmp/ccVyiMyg.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/cczxJRmh.o:factories.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccVyiMyg.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