답안 #427249

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
427249	2021-06-14T13:48:00 Z	model_code	Corporate life (after hostile takover) (CPSPC17_corpo)	C++17	컴파일 오류	0 ms	0 KB

Main

/*
    Autor: Lukasz Marecik
    
    Rozwiazanie wzorcowe nr 1.
    Pomysl AT + moja optymalizacja.
    Zlozonosc: O(n log n).
*/
# include <vector>
# include <queue>
# include <algorithm>
# include <cassert>
# include <string>
# include <iostream>

using namespace std ;
typedef long long LL ;
typedef pair<int,int> PII ;
typedef vector<int> VI ;
const int INF = 1e9+100 ;
const LL INFLL = (LL)INF*INF ;
#define REP(i,n) for(int i=0;i<(n);++i)
#define ALL(c) c.begin(),c.end()
#define FOREACH(i,c) for(auto i=(c).begin();i!=(c).end();++i)
#define CLEAR(t) memset(t,0,sizeof(t))
#define PB push_back
#define MP make_pair
#define FI first
#define SE second

////////////////////////////////////////////////////////////////////////////////

// Ubogie drzewo sum.
// obsluguje:
//  - aktualizacje konkretnego indeksu
//  - zapytanie o sume na spojnym przedziale

class PoorSumTree {
	int n ;
	int *d ;
 public:
	void set(int i, int add) {
		i += n-1 ;
		d[i] += add ;
		for(i>>=1 ; i>0 ; i>>=1)
			d[i] += add ;
	}
	int get(int from) {
		int ret(0) ;
		int i=from+n-1 ;
		do {
			i >>= __builtin_ctz(i) ;
			ret += d[i] ;
			i++ ;
		} while(i&(i-1)) ;
		return ret ;
	}
	int get(int from, int to) {
	    if(from>to) return 0 ;
		return get(from) - ((to<n) ? get(to+1) : 0) ;
	}
	
	PoorSumTree(int size) {     // reprezentuje przedzial [1,..,size]
		n=1 ;
		while(n<size) n<<=1 ;
		d = new int[2*n]() ;
	}
	~PoorSumTree() {
		delete [] d ;
	}
} ;

////////////////////////////////////////////////////////////////////////////////

const int MAXN=2e5+100 ;

VI G1[MAXN] ;
VI G2[MAXN] ;

///////////////////////////////

// PIERWSZA FAZA obliczen: numerowanie POST-ORDER wierzcholkow w obu drzewach
struct Node {
    int id ;        // numer wierzcholka w postorder
    int a, b ;      // [a,b] to przedzial jaki tworza numery wierzcholkow w tym poddrzewie
} ;
Node info1[MAXN] ;
Node info2[MAXN] ;

int whoHasId[MAXN] ;    // odwrotne zaleznosci z pierwszego drzewa
VI  whoHasA [MAXN] ;
VI  whoHasB [MAXN] ;

int size[MAXN], ans[MAXN] ;

int nextNr=1 ;

void calcTree1Info(int u) {
    info1[u].a = nextNr ;
    FOREACH(it, G1[u])
        calcTree1Info(*it) ;
    info1[u].b = nextNr-1 ;
    info1[u].id = nextNr++ ;
    
    whoHasId[info1[u].id] = u ;
    whoHasA [info1[u].a].PB(u) ;
    whoHasB [info1[u].b].PB(u) ;
}

void calcTree2Info(int u) {
    size[u]=1 ;
    info2[u].a = nextNr ;
    FOREACH(it, G2[u]) {
        calcTree2Info(*it) ;
        size[u] += size[*it] ;
    }
    info2[u].b = nextNr-1 ;
    info2[u].id = nextNr++ ;
    
    ans[u] = size[u]-1 ;
}

///////////////////////////////

int main()
{
    ios_base::sync_with_stdio(0) ;
    int n, a, b ;
    
    // wczytywanie danych
    cin >> n ;
    for(int i=2 ; i<=n ; i++) {
        cin >> a ;
        G1[a].PB(i) ;
    }
    for(int i=2 ; i<=n ; i++) {
        cin >> b ;
        G2[b].PB(i) ;
    }
    
    // obliczenia
    nextNr=1 ; calcTree1Info(1) ;
    nextNr=1 ; calcTree2Info(1) ;
    
    PoorSumTree *T = new PoorSumTree(n) ;
    for(int i=1 ; i<=n ; i++) {
        FOREACH(it, whoHasA[i])
            ans[*it] -= T->get(info2[*it].a, info2[*it].b) ;
        T->set(info2[whoHasId[i]].id, 1) ;
    }
    
    delete T ;
    T = new PoorSumTree(n) ;
    for(int i=n ; i>=0 ; i--) {
        FOREACH(it, whoHasB[i])
            ans[*it] -= T->get(info2[*it].a, info2[*it].b) ;
        if(i>0)
            T->set(info2[whoHasId[i]].id, 1) ;
    }
    
    // wypisywanie wyniku
    for(int i=1 ; i<=n ; i++)
        cout << ans[i] << " " ;
    cout << endl ;
}

Compilation message

Main.cpp: In function 'void calcTree2Info(int)':
Main.cpp:110:5: error: reference to 'size' is ambiguous
  110 |     size[u]=1 ;
      |     ^~~~
In file included from /usr/include/c++/10/vector:69,
                 from Main.cpp:8:
/usr/include/c++/10/bits/range_access.h:254:5: note: candidates are: 'template<class _Tp, long unsigned int _Nm> constexpr std::size_t std::size(const _Tp (&)[_Nm])'
  254 |     size(const _Tp (&)[_Nm]) noexcept
      |     ^~~~
/usr/include/c++/10/bits/range_access.h:245:5: note:                 'template<class _Container> constexpr decltype (__cont.size()) std::size(const _Container&)'
  245 |     size(const _Container& __cont) noexcept(noexcept(__cont.size()))
      |     ^~~~
Main.cpp:93:5: note:                 'int size [200100]'
   93 | int size[MAXN], ans[MAXN] ;
      |     ^~~~
Main.cpp:114:9: error: reference to 'size' is ambiguous
  114 |         size[u] += size[*it] ;
      |         ^~~~
In file included from /usr/include/c++/10/vector:69,
                 from Main.cpp:8:
/usr/include/c++/10/bits/range_access.h:254:5: note: candidates are: 'template<class _Tp, long unsigned int _Nm> constexpr std::size_t std::size(const _Tp (&)[_Nm])'
  254 |     size(const _Tp (&)[_Nm]) noexcept
      |     ^~~~
/usr/include/c++/10/bits/range_access.h:245:5: note:                 'template<class _Container> constexpr decltype (__cont.size()) std::size(const _Container&)'
  245 |     size(const _Container& __cont) noexcept(noexcept(__cont.size()))
      |     ^~~~
Main.cpp:93:5: note:                 'int size [200100]'
   93 | int size[MAXN], ans[MAXN] ;
      |     ^~~~
Main.cpp:114:20: error: reference to 'size' is ambiguous
  114 |         size[u] += size[*it] ;
      |                    ^~~~
In file included from /usr/include/c++/10/vector:69,
                 from Main.cpp:8:
/usr/include/c++/10/bits/range_access.h:254:5: note: candidates are: 'template<class _Tp, long unsigned int _Nm> constexpr std::size_t std::size(const _Tp (&)[_Nm])'
  254 |     size(const _Tp (&)[_Nm]) noexcept
      |     ^~~~
/usr/include/c++/10/bits/range_access.h:245:5: note:                 'template<class _Container> constexpr decltype (__cont.size()) std::size(const _Container&)'
  245 |     size(const _Container& __cont) noexcept(noexcept(__cont.size()))
      |     ^~~~
Main.cpp:93:5: note:                 'int size [200100]'
   93 | int size[MAXN], ans[MAXN] ;
      |     ^~~~
Main.cpp:119:14: error: reference to 'size' is ambiguous
  119 |     ans[u] = size[u]-1 ;
      |              ^~~~
In file included from /usr/include/c++/10/vector:69,
                 from Main.cpp:8:
/usr/include/c++/10/bits/range_access.h:254:5: note: candidates are: 'template<class _Tp, long unsigned int _Nm> constexpr std::size_t std::size(const _Tp (&)[_Nm])'
  254 |     size(const _Tp (&)[_Nm]) noexcept
      |     ^~~~
/usr/include/c++/10/bits/range_access.h:245:5: note:                 'template<class _Container> constexpr decltype (__cont.size()) std::size(const _Container&)'
  245 |     size(const _Container& __cont) noexcept(noexcept(__cont.size()))
      |     ^~~~
Main.cpp:93:5: note:                 'int size [200100]'
   93 | int size[MAXN], ans[MAXN] ;
      |     ^~~~