Submission #532361

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

This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.

factories

#include <bits/stdc++.h>
using namespace std;
#include "factories.h"

const int MAX = 6e5;
const long long OO = 0x3f3f3f3f3f3f3f3f;

#define ii pair<int, int>
#define f first
#define s second

int n, max_log;
vector<ii> G[MAX];
int anc[MAX][22], depth[MAX];
long long ans[MAX], weight[MAX];
int CD[MAX], sz[MAX];
bool cut[MAX];

void dfs(int v, int p, int d)
{
    anc[v][0] = p;
    depth[v] = d;
    if(d) max_log = max(max_log, (int)log2(d));
    for(auto [u, w] : G[v]) {
        if(u != p) {
			weight[u] = weight[v] + w;
            dfs(u, v, d + 1);
		}
	}
}

void build()
{
    memset(anc, -1, sizeof(anc));
    dfs(0, -1, 0);  
    for(int j = 1; j <= max_log; j++)
        for(int i = 0; i < n; i++)
            if(anc[i][j-1] != -1)
                anc[i][j] = anc[anc[i][j-1]][j-1];
}

int walk(int v, int k)
{
    while(k)
        v = anc[v][(int)(log2(k & -k))], k -= (k&-k);
    return v;
}

int lca(int u, int v)
{
    if(depth[u] > depth[v]) u = walk(u, depth[u] - depth[v]);
    if(depth[u] < depth[v]) v = walk(v, depth[v] - depth[u]);
    if(u == v) return u;
    for(int i = max_log; i >= 0; i--)
        if(anc[u][i] != anc[v][i])
        {
            u = anc[u][i];
            v = anc[v][i];
        }
    return anc[u][0];
}

int dfs2(int v, int p)
{
    int s = 1;
    for(auto [u, w] : G[v])
        if(!cut[u] and u != p)
            s += dfs2(u, v);
    return sz[v] = s;
}

int find_centroid(int v, int p, int tot)
{
    int next_v, cnt = 0;
    for(auto [u, w] : G[v])
        if(!cut[u] and u != p and sz[u] > cnt)
            cnt = sz[u], next_v = u;
    if(cnt > tot / 2) return find_centroid(next_v, v, tot);
    return v;
}

void build_centroid_tree(int v, int p)
{
    dfs2(v, -1);
    int u = find_centroid(v, -1, sz[v]);
    CD[u] = p;
    cut[u] = true;
    for(auto [w, h] : G[u])
        if(!cut[w])
            build_centroid_tree(w, u);
}

int dist(int u, int v)
{
    return weight[u] + weight[v] - 2*weight[lca(u, v)];
}

void paint(int v, int u)
{
    if(v == -1) return;
    ans[v] = min(ans[v], dist(v, u));
    paint(CD[v], u);
}

void unpaint(int v, int u)
{
    if(v == -1) return;
    ans[v] = OO;
    paint(CD[v], u);
}

int query(int v, int u, int d)
{
    if(v == -1)
        return d;
    return query(CD[v], u, min(d, dist(v, u) + ans[v]));
}

void Init(int N, int A[], int B[], int D[]) {
	n = N;
	for(int i = 0; i < n-1; i++) {
        G[ A[i] ].push_back({B[i], D[i]});
        G[ B[i] ].push_back({A[i], D[i]});
    }
	build(); 
    build_centroid_tree(0, -1);
    memset(ans, 63, sizeof(ans));
}

long long Query(int S, int X[], int T, int Y[]) {
	for(int j = 0; j < S; ++j) 
		paint(X[j], X[j]);
	long long rep = OO;
	for(int j = 0; j < T; ++j) {
		rep = min(rep, query(Y[j], Y[j], OO));
	}
	for(int j = 0; j < S; ++j) 
		unpaint(X[j], X[j]);
	return rep;
}

Compilation message (stderr)

factories.cpp: In function 'void paint(int, int)':
factories.cpp:101:36: error: no matching function for call to 'min(long long int&, int)'
  101 |     ans[v] = min(ans[v], dist(v, u));
      |                                    ^
In file included from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from factories.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:230:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::min(const _Tp&, const _Tp&)'
  230 |     min(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:230:5: note:   template argument deduction/substitution failed:
factories.cpp:101:36: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and 'int')
  101 |     ans[v] = min(ans[v], dist(v, u));
      |                                    ^
In file included from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from factories.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:278:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::min(const _Tp&, const _Tp&, _Compare)'
  278 |     min(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:278:5: note:   template argument deduction/substitution failed:
factories.cpp:101:36: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and 'int')
  101 |     ans[v] = min(ans[v], dist(v, u));
      |                                    ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from factories.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:3468:5: note: candidate: 'template<class _Tp> constexpr _Tp std::min(std::initializer_list<_Tp>)'
 3468 |     min(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3468:5: note:   template argument deduction/substitution failed:
factories.cpp:101:36: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long int'
  101 |     ans[v] = min(ans[v], dist(v, u));
      |                                    ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from factories.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:3474:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::min(std::initializer_list<_Tp>, _Compare)'
 3474 |     min(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3474:5: note:   template argument deduction/substitution failed:
factories.cpp:101:36: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long int'
  101 |     ans[v] = min(ans[v], dist(v, u));
      |                                    ^
factories.cpp: In function 'int query(int, int, int)':
factories.cpp:116:54: error: no matching function for call to 'min(int&, long long int)'
  116 |     return query(CD[v], u, min(d, dist(v, u) + ans[v]));
      |                                                      ^
In file included from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from factories.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:230:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::min(const _Tp&, const _Tp&)'
  230 |     min(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:230:5: note:   template argument deduction/substitution failed:
factories.cpp:116:54: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'long long int')
  116 |     return query(CD[v], u, min(d, dist(v, u) + ans[v]));
      |                                                      ^
In file included from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from factories.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:278:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::min(const _Tp&, const _Tp&, _Compare)'
  278 |     min(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:278:5: note:   template argument deduction/substitution failed:
factories.cpp:116:54: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'long long int')
  116 |     return query(CD[v], u, min(d, dist(v, u) + ans[v]));
      |                                                      ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from factories.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:3468:5: note: candidate: 'template<class _Tp> constexpr _Tp std::min(std::initializer_list<_Tp>)'
 3468 |     min(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3468:5: note:   template argument deduction/substitution failed:
factories.cpp:116:54: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
  116 |     return query(CD[v], u, min(d, dist(v, u) + ans[v]));
      |                                                      ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from factories.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:3474:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::min(std::initializer_list<_Tp>, _Compare)'
 3474 |     min(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3474:5: note:   template argument deduction/substitution failed:
factories.cpp:116:54: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
  116 |     return query(CD[v], u, min(d, dist(v, u) + ans[v]));
      |                                                      ^
factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:135:36: warning: overflow in conversion from 'long long int' to 'int' changes value from '4557430888798830399' to '1061109567' [-Woverflow]
  135 |   rep = min(rep, query(Y[j], Y[j], OO));
      |                                    ^~
factories.cpp:135:39: error: no matching function for call to 'min(long long int&, int)'
  135 |   rep = min(rep, query(Y[j], Y[j], OO));
      |                                       ^
In file included from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from factories.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:230:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::min(const _Tp&, const _Tp&)'
  230 |     min(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:230:5: note:   template argument deduction/substitution failed:
factories.cpp:135:39: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and 'int')
  135 |   rep = min(rep, query(Y[j], Y[j], OO));
      |                                       ^
In file included from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from factories.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:278:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::min(const _Tp&, const _Tp&, _Compare)'
  278 |     min(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:278:5: note:   template argument deduction/substitution failed:
factories.cpp:135:39: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and 'int')
  135 |   rep = min(rep, query(Y[j], Y[j], OO));
      |                                       ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from factories.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:3468:5: note: candidate: 'template<class _Tp> constexpr _Tp std::min(std::initializer_list<_Tp>)'
 3468 |     min(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3468:5: note:   template argument deduction/substitution failed:
factories.cpp:135:39: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long int'
  135 |   rep = min(rep, query(Y[j], Y[j], OO));
      |                                       ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from factories.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:3474:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::min(std::initializer_list<_Tp>, _Compare)'
 3474 |     min(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3474:5: note:   template argument deduction/substitution failed:
factories.cpp:135:39: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long int'
  135 |   rep = min(rep, query(Y[j], Y[j], OO));
      |                                       ^