oj.uz

Submission #427255

# Submission time Handle Problem Language Result Execution time Memory
427255 2021-06-14T13:49:02 Z model_code Corporate life (after hostile takover) (CPSPC17_corpo) C++
100 / 100
 396 ms 58616 KB 
/*
    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 ;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 19148 KB Output is correct
2 Correct 13 ms 19120 KB Output is correct
3 Correct 12 ms 19052 KB Output is correct
4 Correct 11 ms 19096 KB Output is correct
5 Correct 12 ms 19148 KB Output is correct
6 Correct 13 ms 19148 KB Output is correct
7 Correct 12 ms 19164 KB Output is correct
8 Correct 12 ms 19268 KB Output is correct
9 Correct 12 ms 19304 KB Output is correct
10 Correct 13 ms 19276 KB Output is correct
11 Correct 12 ms 19208 KB Output is correct
12 Correct 13 ms 19276 KB Output is correct
13 Correct 12 ms 19228 KB Output is correct
14 Correct 14 ms 19276 KB Output is correct
15 Correct 13 ms 19396 KB Output is correct
16 Correct 14 ms 19348 KB Output is correct
17 Correct 13 ms 19404 KB Output is correct
18 Correct 13 ms 19404 KB Output is correct
19 Correct 13 ms 19456 KB Output is correct
20 Correct 13 ms 19404 KB Output is correct
21 Correct 13 ms 19436 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 19148 KB Output is correct
2 Correct 13 ms 19120 KB Output is correct
3 Correct 12 ms 19052 KB Output is correct
4 Correct 11 ms 19096 KB Output is correct
5 Correct 12 ms 19148 KB Output is correct
6 Correct 13 ms 19148 KB Output is correct
7 Correct 12 ms 19164 KB Output is correct
8 Correct 12 ms 19268 KB Output is correct
9 Correct 12 ms 19304 KB Output is correct
10 Correct 13 ms 19276 KB Output is correct
11 Correct 12 ms 19208 KB Output is correct
12 Correct 13 ms 19276 KB Output is correct
13 Correct 12 ms 19228 KB Output is correct
14 Correct 14 ms 19276 KB Output is correct
15 Correct 13 ms 19396 KB Output is correct
16 Correct 14 ms 19348 KB Output is correct
17 Correct 13 ms 19404 KB Output is correct
18 Correct 13 ms 19404 KB Output is correct
19 Correct 13 ms 19456 KB Output is correct
20 Correct 13 ms 19404 KB Output is correct
21 Correct 13 ms 19436 KB Output is correct
22 Correct 129 ms 33972 KB Output is correct
23 Correct 147 ms 35348 KB Output is correct
24 Correct 156 ms 36968 KB Output is correct
25 Correct 124 ms 33984 KB Output is correct
26 Correct 156 ms 38652 KB Output is correct
27 Correct 135 ms 38720 KB Output is correct
28 Correct 130 ms 38696 KB Output is correct
29 Correct 396 ms 47448 KB Output is correct
30 Correct 346 ms 50204 KB Output is correct
31 Correct 335 ms 53212 KB Output is correct
32 Correct 288 ms 47140 KB Output is correct
33 Correct 320 ms 56584 KB Output is correct
34 Correct 310 ms 56628 KB Output is correct
35 Correct 339 ms 56612 KB Output is correct
36 Correct 365 ms 48920 KB Output is correct
37 Correct 386 ms 51920 KB Output is correct
38 Correct 344 ms 54872 KB Output is correct
39 Correct 314 ms 48736 KB Output is correct
40 Correct 313 ms 58392 KB Output is correct
41 Correct 316 ms 58616 KB Output is correct
42 Correct 330 ms 58288 KB Output is correct