Submission #13295

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
13295	2015-02-10T13:18:41 Z	gs14004	Factories (JOI14_factories)	C++14	Compilation error	0 ms	0 KB

factories

#include "factories.h"
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;
typedef long long lint;
typedef pair<int,int> pi;
typedef pair<int,lint> pi2;
typedef pair<lint,lint> pi3;

vector<pi> graph[500005];

int piv, dfn[500005];
int dep[500005];
lint dist[500005];
int pa[500005][20];
int type[500005];

void dfs(int x, int par, int d, lint t){
    dep[x] = d;
    dfn[x] = ++piv;
    dist[x] = t;
    pa[x][0] = par;
    for (int i=1; i<20; i++) {
        pa[x][i] = pa[pa[x][i-1]][i-1];
    }
    for (pi &i : graph[x]){
        if(par == i.second) continue;
        dfs(i.second,x,d+1,t + i.first);
    }
}

void Init(int N, int A[], int B[], int D[]){
    memset(type,-1,sizeof(type));
    for (int i=0; i<N-1; i++) {
        graph[A[i]].push_back(pi(D[i],B[i]));
        graph[B[i]].push_back(pi(D[i],A[i]));
    }
    dfs(1,0,0,0);
}

int lca(int x, int y){
    if(dep[x] < dep[y]) swap(x,y);
    int dx = dep[x] - dep[y];
    for (int i=0; (1<<i) <= dx; i++) {
        if(dx & (1<<i)) {
            x = pa[x][i];
        }
    }
    for (int i=19; i>=0; i--) {
        if(pa[x][i] != pa[y][i]){
            x = pa[x][i];
            y = pa[y][i];
        }
    }
    if(x != y) x = pa[x][0];
    return x;
}

bool cmp(pi a, pi b){
    return dfn[a.first] < dfn[b.first];
}

vector<pi2> g2[500005];

lint ret;

pi3 dfs2(int x, int par, lint dist0, lint dist1){
    lint ret0_min = 1e18;
    lint ret1_min = 1e18;
    if(type[x] == 0) dist0 = ret0_min = 0;
    if(type[x] == 1) dist1 = ret1_min = 0;
    for (pi2 &i : g2[x]){
        if(i.first == par) continue;
        pi3 t = dfs2(i.first,x,dist0 + i.second,dist1 + i.second);
        ret0_min = min(ret,t.first + i.second);
        ret1_min = min(ret,t.second + i.second);
    }
    dist0 = min(dist0,ret0_min);
    dist1 = min(dist1,ret1_min);
    ret = min(dist0 + dist1,ret);
    return pi3(ret0_min,ret1_min);
}

lint Query(int S, int X[], int T, int Y[]){
    vector<int> used;
    for (int i=0; i<S; i++) {
        type[X[i]] = 0;
        used.push_back(X[i]);
    }
    for (int i=0; i<T; i++) {
        type[Y[i]] = 1;
        used.push_back(Y[i]);
    }
    sort(used.begin(),used.end(),cmp);
    for (int i=0; i<used.size() - 1; i++) {
        int l = lca(used[i],used[i+1]);
        if(l != used[i]){
            g2[l].push_back(pi2(used[i],dist[used[i]] - dist[l]));
            g2[used[i]].push_back(pi2(l,dist[used[i]] - dist[l]));
        }
        if(l != used[i+1]){
            g2[l].push_back(pi2(used[i+1],dist[used[i+1]] - dist[l]));
            g2[used[i+1]].push_back(pi2(l,dist[used[i+1]] - dist[l]));
        }
        used.push_back(l);
    }
    dfs2(used[0],0,1e18,1e18);
    for (int i=0; i<S; i++) {
        type[X[i]] = -1;
    }
    for (int i=0; i<T; i++) {
        type[Y[i]] = -1;
    }
    for (int &i : used){
        g2[i].clear();
    }
    return ret;
}

Compilation message

factories.cpp: In function ‘void Init(int, int*, int*, int*)’:
factories.cpp:34:32: error: ‘memset’ was not declared in this scope
     memset(type,-1,sizeof(type));
                                ^
factories.cpp: In function ‘lint Query(int, int*, int, int*)’:
factories.cpp:96:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0; i<used.size() - 1; i++) {
                    ^
In file included from /usr/include/c++/4.9/bits/stl_algobase.h:71:0,
                 from /usr/include/c++/4.9/vector:60,
                 from factories.cpp:2:
/usr/include/c++/4.9/bits/predefined_ops.h: In instantiation of ‘bool __gnu_cxx::__ops::_Iter_comp_iter<_Compare>::operator()(_Iterator1, _Iterator2) [with _Iterator1 = __gnu_cxx::__normal_iterator<int*, std::vector<int> >; _Iterator2 = __gnu_cxx::__normal_iterator<int*, std::vector<int> >; _Compare = bool (*)(std::pair<int, int>, std::pair<int, int>)]’:
/usr/include/c++/4.9/bits/stl_algo.h:1846:27:   required from ‘void std::__insertion_sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<int*, std::vector<int> >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<bool (*)(std::pair<int, int>, std::pair<int, int>)>]’
/usr/include/c++/4.9/bits/stl_algo.h:1884:70:   required from ‘void std::__final_insertion_sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<int*, std::vector<int> >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<bool (*)(std::pair<int, int>, std::pair<int, int>)>]’
/usr/include/c++/4.9/bits/stl_algo.h:1970:55:   required from ‘void std::__sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<int*, std::vector<int> >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<bool (*)(std::pair<int, int>, std::pair<int, int>)>]’
/usr/include/c++/4.9/bits/stl_algo.h:4716:78:   required from ‘void std::sort(_RAIter, _RAIter, _Compare) [with _RAIter = __gnu_cxx::__normal_iterator<int*, std::vector<int> >; _Compare = bool (*)(std::pair<int, int>, std::pair<int, int>)]’
factories.cpp:95:37:   required from here
/usr/include/c++/4.9/bits/predefined_ops.h:121:46: error: could not convert ‘__it1.__gnu_cxx::__normal_iterator<_Iterator, _Container>::operator*<int*, std::vector<int> >()’ from ‘int’ to ‘std::pair<int, int>’
         { return bool(_M_comp(*__it1, *__it2)); }
                                              ^
/usr/include/c++/4.9/bits/predefined_ops.h: In instantiation of ‘bool __gnu_cxx::__ops::_Val_comp_iter<_Compare>::operator()(_Value&, _Iterator) [with _Value = int; _Iterator = __gnu_cxx::__normal_iterator<int*, std::vector<int> >; _Compare = bool (*)(std::pair<int, int>, std::pair<int, int>)]’:
/usr/include/c++/4.9/bits/stl_algo.h:1827:34:   required from ‘void std::__unguarded_linear_insert(_RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<int*, std::vector<int> >; _Compare = __gnu_cxx::__ops::_Val_comp_iter<bool (*)(std::pair<int, int>, std::pair<int, int>)>]’
/usr/include/c++/4.9/bits/stl_algo.h:1855:46:   required from ‘void std::__insertion_sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<int*, std::vector<int> >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<bool (*)(std::pair<int, int>, std::pair<int, int>)>]’
/usr/include/c++/4.9/bits/stl_algo.h:1884:70:   required from ‘void std::__final_insertion_sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<int*, std::vector<int> >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<bool (*)(std::pair<int, int>, std::pair<int, int>)>]’
/usr/include/c++/4.9/bits/stl_algo.h:1970:55:   required from ‘void std::__sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<int*, std::vector<int> >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<bool (*)(std::pair<int, int>, std::pair<int, int>)>]’
/usr/include/c++/4.9/bits/stl_algo.h:4716:78:   required from ‘void std::sort(_RAIter, _RAIter, _Compare) [with _RAIter = __gnu_cxx::__normal_iterator<int*, std::vector<int> >; _Compare = bool (*)(std::pair<int, int>, std::pair<int, int>)]’
factories.cpp:95:37:   required from here
/usr/include/c++/4.9/bits/predefined_ops.h:166:37: error: could not convert ‘__val’ from ‘int’ to ‘std::pair<int, int>’
  { return bool(_M_comp(__val, *__it)); }
                                     ^
/usr/include/c++/4.9/bits/predefined_ops.h: In instantiation of ‘bool __gnu_cxx::__ops::_Iter_comp_val<_Compare>::operator()(_Iterator, _Value&) [with _Iterator = __gnu_cxx::__normal_iterator<int*, std::vector<int> >; _Value = int; _Compare = bool (*)(std::pair<int, int>, std::pair<int, int>)]’:
/usr/include/c++/4.9/bits/stl_heap.h:129:76:   required from ‘void std::__push_heap(_RandomAccessIterator, _Distance, _Distance, _Tp, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<int*, std::vector<int> >; _Distance = long int; _Tp = int; _Compare = __gnu_cxx::__ops::_Iter_comp_val<bool (*)(std::pair<int, int>, std::pair<int, int>)>]’
/usr/include/c++/4.9/bits/stl_heap.h:230:51:   required from ‘void std::__adjust_heap(_RandomAccessIterator, _Distance, _Distance, _Tp, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<int*, std::vector<int> >; _Distance = long int; _Tp = int; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<bool (*)(std::pair<int, int>, std::pair<int, int>)>]’
/usr/include/c++/4.9/bits/stl_heap.h:334:15:   required from ‘void std::__make_heap(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<int*, std::vector<int> >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<bool (*)(std::pair<int, int>, std::pair<int, int>)>]’
/usr/include/c++/4.9/bits/stl_algo.h:1673:49:   required from ‘void std::__heap_select(_RandomAccessIterator, _RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<int*, std::vector<int> >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<bool (*)(std::pair<int, int>, std::pair<int, int>)>]’
/usr/include/c++/4.9/bits/stl_algo.h:1932:59:   required from ‘void std::__partial_sort(_RandomAccessIterator, _RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<int*, std::vector<int> >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<bool (*)(std::pair<int, int>, std::pair<int, int>)>]’
/usr/include/c++/4.9/bits/stl_algo.h:1947:59:   required from ‘void std::__introsort_loop(_RandomAccessIterator, _RandomAccessIterator, _Size, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<int*, std::vector<int> >; _Size = long int; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<bool (*)(std::pair<int, int>, std::pair<int, int>)>]’
/usr/include/c++/4.9/bits/stl_algo.h:1969:11:   required from ‘void std::__sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<int*, std::vector<int> >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<bool (*)(std::pair<int, int>, std::pair<int, int>)>]’
/usr/include/c++/4.9/bits/stl_algo.h:4716:78:   required from ‘void std::sort(_RAIter, _RAIter, _Compare) [with _RAIter = __gnu_cxx::__normal_iterator<int*, std::vector<int> >; _Compare = bool (*)(std::pair<int, int>, std::pair<int, int>)]’
factories.cpp:95:37:   required from here
/usr/include/c++/4.9/bits/predefined_ops.h:141:37: error: could not convert ‘__it.__gnu_cxx::__normal_iterator<_Iterator, _Container>::operator*<int*, std::vector<int> >()’ from ‘int’ to ‘std::pair<int, int>’
  { return bool(_M_comp(*__it, __val)); }
                                     ^