| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 656760 | anhduc2701 | 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.
#include<bits/stdc++.h>
#include "factories.h"
#define int long long
using namespace std;
typedef long long ll;
const ll INF=1e18;
const int maxn=1e6+5;
const int mod=1e9+7;
const int mo=998244353;
using pi=pair<ll,ll>;
using vi=vector<ll>;
using pii=pair<pair<ll,ll>,ll>;
#define all(x) x.begin(), x.end()
#define len(x) ll(x.size())
#define eb emplace_back
#define PI 3.14159265359
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define MIN(v) *min_element(all(v))
#define MAX(v) *max_element(all(v))
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int n;
set<pair<int,int>>G[500005];
int sz[500005];
int pa[500005];
int dfsz(int u,int p){
sz[u]=1;
for(auto v.first:G[u]){
if(v.first!=p){
sz[u]+=dfsz(v.first,u);
}
}
return sz[u];
}
int centroid(int u,int p,int n){
for(auto v:G[u]){
if(v.first!=p){
if(sz[v.first]>n/2)return centroid(v.first,u,n);
}
}
return u;
}
void dfs2(int u,int p,int c,int d){
dis[c][u]=0;
for(auto v:G[u]){
if(v.first!=p){
dfs2(v.first,u,c,d+v.second);
}
}
}
void upd(int u){
int v=u;
while(v!=0){
ans[v]=min(ans[v],dis[v][u]);
v=pa[v];
}
}
int query(int u){
int mi=INF;
int v=u;
while(v!=0){
mi=min(ans[v]+dis[v][u],mi);
v=pa[v];
}
return mi;
}
void build(int u,int p){
int n1=dfsz(u,p);
int c=centroid(u,p,n1);
if(p==-1)p=c;
pa[c]=p;
dfs2(c,p,c,0);
vector<int>tmp(G[c].begin(),G[c].end());
for(auto v:tmp){
G[c].erase({v.first,v.second});
G[v].erase({c.first,v.second});
build(v,c);
}
}
void Init(int N,int A[],int B[],int D[]){
n=N;
for(int i=0;i<N;i++){
G[A[i]+1].pb({B[i]+1,D[i]});
G[B[i]+1].pb({A[i]+1,D[i]});
}
build(0,-1);
}
long long Query(int S,int X[],int T,int Y[]){
for(int i=1;i<=n;i++){
ans[i]=INF;
}
for(int i=0;i<S;i++){
upd(X[i]+1);
}
int an=INF;
for(int i=0;i<T;i++){
an=min(an,query(Y[i]+1));
}
return an;
}
Compilation message (stderr)
factories.cpp: In function 'long long int dfsz(long long int, long long int)':
factories.cpp:30:12: error: expected ';' before '.' token
30 | for(auto v.first:G[u]){
| ^
| ;
factories.cpp:30:12: error: expected primary-expression before '.' token
factories.cpp:30:18: error: found ':' in nested-name-specifier, expected '::'
30 | for(auto v.first:G[u]){
| ^
| ::
factories.cpp:30:13: error: request for member 'first' in non-class type '<type error>'
30 | for(auto v.first:G[u]){
| ^~~~~
factories.cpp:30:23: error: expected ';' before ')' token
30 | for(auto v.first:G[u]){
| ^
| ;
factories.cpp:31:6: error: use of 'v' before deduction of 'auto'
31 | if(v.first!=p){
| ^
factories.cpp:32:16: error: use of 'v' before deduction of 'auto'
32 | sz[u]+=dfsz(v.first,u);
| ^
factories.cpp: In function 'void dfs2(long long int, long long int, long long int, long long int)':
factories.cpp:46:2: error: 'dis' was not declared in this scope; did you mean 'div'?
46 | dis[c][u]=0;
| ^~~
| div
factories.cpp: In function 'void upd(long long int)':
factories.cpp:56:3: error: 'ans' was not declared in this scope; did you mean 'abs'?
56 | ans[v]=min(ans[v],dis[v][u]);
| ^~~
| abs
factories.cpp:56:21: error: 'dis' was not declared in this scope; did you mean 'div'?
56 | ans[v]=min(ans[v],dis[v][u]);
| ^~~
| div
factories.cpp: In function 'long long int query(long long int)':
factories.cpp:64:10: error: 'ans' was not declared in this scope; did you mean 'abs'?
64 | mi=min(ans[v]+dis[v][u],mi);
| ^~~
| abs
factories.cpp:64:17: error: 'dis' was not declared in this scope; did you mean 'div'?
64 | mi=min(ans[v]+dis[v][u],mi);
| ^~~
| div
factories.cpp: In function 'void build(long long int, long long int)':
factories.cpp:77:17: error: request for member 'first' in 'v', which is of non-class type 'long long int'
77 | G[c].erase({v.first,v.second});
| ^~~~~
factories.cpp:77:25: error: request for member 'second' in 'v', which is of non-class type 'long long int'
77 | G[c].erase({v.first,v.second});
| ^~~~~~
factories.cpp:77:32: error: no matching function for call to 'std::set<std::pair<long long int, long long int> >::erase(<brace-enclosed initializer list>)'
77 | G[c].erase({v.first,v.second});
| ^
In file included from /usr/include/c++/10/set:61,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:87,
from factories.cpp:1:
/usr/include/c++/10/bits/stl_set.h:654:7: note: candidate: 'std::set<_Key, _Compare, _Alloc>::iterator std::set<_Key, _Compare, _Alloc>::erase(std::set<_Key, _Compare, _Alloc>::const_iterator) [with _Key = std::pair<long long int, long long int>; _Compare = std::less<std::pair<long long int, long long int> >; _Alloc = std::allocator<std::pair<long long int, long long int> >; std::set<_Key, _Compare, _Alloc>::iterator = std::_Rb_tree<std::pair<long long int, long long int>, std::pair<long long int, long long int>, std::_Identity<std::pair<long long int, long long int> >, std::less<std::pair<long long int, long long int> >, std::allocator<std::pair<long long int, long long int> > >::const_iterator; std::set<_Key, _Compare, _Alloc>::const_iterator = std::_Rb_tree<std::pair<long long int, long long int>, std::pair<long long int, long long int>, std::_Identity<std::pair<long long int, long long int> >, std::less<std::pair<long long int, long long int> >, std::allocator<std::pair<long long int, long long int> > >::const_iterator]'
654 | erase(const_iterator __position)
| ^~~~~
/usr/include/c++/10/bits/stl_set.h:654:28: note: no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'std::set<std::pair<long long int, long long int> >::const_iterator' {aka 'std::_Rb_tree<std::pair<long long int, long long int>, std::pair<long long int, long long int>, std::_Identity<std::pair<long long int, long long int> >, std::less<std::pair<long long int, long long int> >, std::allocator<std::pair<long long int, long long int> > >::const_iterator'}
654 | erase(const_iterator __position)
| ~~~~~~~~~~~~~~~^~~~~~~~~~
/usr/include/c++/10/bits/stl_set.h:684:7: note: candidate: 'std::set<_Key, _Compare, _Alloc>::size_type std::set<_Key, _Compare, _Alloc>::erase(const key_type&) [with _Key = std::pair<long long int, long long int>; _Compare = std::less<std::pair<long long int, long long int> >; _Alloc = std::allocator<std::pair<long long int, long long int> >; std::set<_Key, _Compare, _Alloc>::size_type = long unsigned int; std::set<_Key, _Compare, _Alloc>::key_type = std::pair<long long int, long long int>]'
684 | erase(const key_type& __x)
| ^~~~~
/usr/include/c++/10/bits/stl_set.h:684:29: note: no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'const key_type&' {aka 'const std::pair<long long int, long long int>&'}
684 | erase(const key_type& __x)
| ~~~~~~~~~~~~~~~~^~~
/usr/include/c++/10/bits/stl_set.h:706:7: note: candidate: 'std::set<_Key, _Compare, _Alloc>::iterator std::set<_Key, _Compare, _Alloc>::erase(std::set<_Key, _Compare, _Alloc>::const_iterator, std::set<_Key, _Compare, _Alloc>::const_iterator) [with _Key = std::pair<long long int, long long int>; _Compare = std::less<std::pair<long long int, long long int> >; _Alloc = std::allocator<std::pair<long long int, long long int> >; std::set<_Key, _Compare, _Alloc>::iterator = std::_Rb_tree<std::pair<long long int, long long int>, std::pair<long long int, long long int>, std::_Identity<std::pair<long long int, long long int> >, std::less<std::pair<long long int, long long int> >, std::allocator<std::pair<long long int, long long int> > >::const_iterator; std::set<_Key, _Compare, _Alloc>::const_iterator = std::_Rb_tree<std::pair<long long int, long long int>, std::pair<long long int, long long int>, std::_Identity<std::pair<long long int, long long int> >, std::less<std::pair<long long int, long long int> >, std::allocator<std::pair<long long int, long long int> > >::const_iterator]'
706 | erase(const_iterator __first, const_iterator __last)
| ^~~~~
/usr/include/c++/10/bits/stl_set.h:706:7: note: candidate expects 2 arguments, 1 provided
factories.cpp:78:17: error: request for member 'first' in 'c', which is of non-class type 'long long int'
78 | G[v].erase({c.first,v.second});
| ^~~~~
factories.cpp:78:25: error: request for member 'second' in 'v', which is of non-class type 'long long int'
78 | G[v].erase({c.first,v.second});
| ^~~~~~
factories.cpp:78:32: error: no matching function for call to 'std::set<std::pair<long long int, long long int> >::erase(<brace-enclosed initializer list>)'
78 | G[v].erase({c.first,v.second});
| ^
In file included from /usr/include/c++/10/set:61,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:87,
from factories.cpp:1:
/usr/include/c++/10/bits/stl_set.h:654:7: note: candidate: 'std::set<_Key, _Compare, _Alloc>::iterator std::set<_Key, _Compare, _Alloc>::erase(std::set<_Key, _Compare, _Alloc>::const_iterator) [with _Key = std::pair<long long int, long long int>; _Compare = std::less<std::pair<long long int, long long int> >; _Alloc = std::allocator<std::pair<long long int, long long int> >; std::set<_Key, _Compare, _Alloc>::iterator = std::_Rb_tree<std::pair<long long int, long long int>, std::pair<long long int, long long int>, std::_Identity<std::pair<long long int, long long int> >, std::less<std::pair<long long int, long long int> >, std::allocator<std::pair<long long int, long long int> > >::const_iterator; std::set<_Key, _Compare, _Alloc>::const_iterator = std::_Rb_tree<std::pair<long long int, long long int>, std::pair<long long int, long long int>, std::_Identity<std::pair<long long int, long long int> >, std::less<std::pair<long long int, long long int> >, std::allocator<std::pair<long long int, long long int> > >::const_iterator]'
654 | erase(const_iterator __position)
| ^~~~~
/usr/include/c++/10/bits/stl_set.h:654:28: note: no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'std::set<std::pair<long long int, long long int> >::const_iterator' {aka 'std::_Rb_tree<std::pair<long long int, long long int>, std::pair<long long int, long long int>, std::_Identity<std::pair<long long int, long long int> >, std::less<std::pair<long long int, long long int> >, std::allocator<std::pair<long long int, long long int> > >::const_iterator'}
654 | erase(const_iterator __position)
| ~~~~~~~~~~~~~~~^~~~~~~~~~
/usr/include/c++/10/bits/stl_set.h:684:7: note: candidate: 'std::set<_Key, _Compare, _Alloc>::size_type std::set<_Key, _Compare, _Alloc>::erase(const key_type&) [with _Key = std::pair<long long int, long long int>; _Compare = std::less<std::pair<long long int, long long int> >; _Alloc = std::allocator<std::pair<long long int, long long int> >; std::set<_Key, _Compare, _Alloc>::size_type = long unsigned int; std::set<_Key, _Compare, _Alloc>::key_type = std::pair<long long int, long long int>]'
684 | erase(const key_type& __x)
| ^~~~~
/usr/include/c++/10/bits/stl_set.h:684:29: note: no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'const key_type&' {aka 'const std::pair<long long int, long long int>&'}
684 | erase(const key_type& __x)
| ~~~~~~~~~~~~~~~~^~~
/usr/include/c++/10/bits/stl_set.h:706:7: note: candidate: 'std::set<_Key, _Compare, _Alloc>::iterator std::set<_Key, _Compare, _Alloc>::erase(std::set<_Key, _Compare, _Alloc>::const_iterator, std::set<_Key, _Compare, _Alloc>::const_iterator) [with _Key = std::pair<long long int, long long int>; _Compare = std::less<std::pair<long long int, long long int> >; _Alloc = std::allocator<std::pair<long long int, long long int> >; std::set<_Key, _Compare, _Alloc>::iterator = std::_Rb_tree<std::pair<long long int, long long int>, std::pair<long long int, long long int>, std::_Identity<std::pair<long long int, long long int> >, std::less<std::pair<long long int, long long int> >, std::allocator<std::pair<long long int, long long int> > >::const_iterator; std::set<_Key, _Compare, _Alloc>::const_iterator = std::_Rb_tree<std::pair<long long int, long long int>, std::pair<long long int, long long int>, std::_Identity<std::pair<long long int, long long int> >, std::less<std::pair<long long int, long long int> >, std::allocator<std::pair<long long int, long long int> > >::const_iterator]'
706 | erase(const_iterator __first, const_iterator __last)
| ^~~~~
/usr/include/c++/10/bits/stl_set.h:706:7: note: candidate expects 2 arguments, 1 provided
factories.cpp: In function 'void Init(long long int, long long int*, long long int*, long long int*)':
factories.cpp:20:12: error: 'class std::set<std::pair<long long int, long long int> >' has no member named 'push_back'
20 | #define pb push_back
| ^~~~~~~~~
factories.cpp:85:13: note: in expansion of macro 'pb'
85 | G[A[i]+1].pb({B[i]+1,D[i]});
| ^~
factories.cpp:20:12: error: 'class std::set<std::pair<long long int, long long int> >' has no member named 'push_back'
20 | #define pb push_back
| ^~~~~~~~~
factories.cpp:86:13: note: in expansion of macro 'pb'
86 | G[B[i]+1].pb({A[i]+1,D[i]});
| ^~
factories.cpp: In function 'long long int Query(long long int, long long int*, long long int, long long int*)':
factories.cpp:92:3: error: 'ans' was not declared in this scope; did you mean 'abs'?
92 | ans[i]=INF;
| ^~~
| abs
In file included from /usr/include/c++/10/vector:66,
from /usr/include/c++/10/functional:62,
from /usr/include/c++/10/pstl/glue_algorithm_defs.h:13,
from /usr/include/c++/10/algorithm:74,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
from factories.cpp:1:
/usr/include/c++/10/bits/stl_uninitialized.h: In instantiation of '_ForwardIterator std::uninitialized_copy(_InputIterator, _InputIterator, _ForwardIterator) [with _InputIterator = std::_Rb_tree_const_iterator<std::pair<long long int, long long int> >; _ForwardIterator = long long int*]':
/usr/include/c++/10/bits/stl_uninitialized.h:325:37: required from '_ForwardIterator std::__uninitialized_copy_a(_InputIterator, _InputIterator, _ForwardIterator, std::allocator<_Tp>&) [with _InputIterator = std::_Rb_tree_const_iterator<std::pair<long long int, long long int> >; _ForwardIterator = long long int*; _Tp = long long int]'
/usr/include/c++/10/bits/stl_vector.h:1585:33: required from 'void std::vector<_Tp, _Alloc>::_M_range_initialize(_ForwardIterator, _ForwardIterator, std::forward_iterator_tag) [with _ForwardIterator = std::_Rb_tree_const_iterator<std::pair<long long int, long long int> >; _Tp = long long int; _Alloc = std::allocator<long long int>]'
/usr/include/c++/10/bits/stl_vector.h:657:23: required from 'std::vector<_Tp, _Alloc>::vector(_InputIterator, _InputIterator, const allocator_type&) [with _InputIterator = std::_Rb_tree_const_iterator<std::pair<long long int, long long int> >; <template-parameter-2-2> = void; _Tp = long long int; _Alloc = std::allocator<long long int>; std::vector<_Tp, _Alloc>::allocator_type = std::allocator<long long int>]'
factories.cpp:75:40: required from here
/usr/include/c++/10/bits/stl_uninitialized.h:137:72: error: static assertion failed: result type must be constructible from value type of input range
137 | static_assert(is_constructible<_ValueType2, decltype(*__first)>::value,
| ^~~~~