oj.uz

Submission #427256

# Submission time Handle Problem Language Result Execution time Memory
427256 2021-06-14T13:49:32 Z model_code Corporate life (after hostile takover) (CPSPC17_corpo) C++
30 / 100
 1000 ms 14532 KB 
/*
    Autor: Lukasz Marecik
    
    Najprostsze rozwiazanie brutalne,
    dzialajace w czasie O(\sum_v subTreeSize(v)) = O(n^2).
*/

#include <bits/stdc++.h>
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

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

const int MAXN=2e5+100 ;

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

int color[MAXN]; 

// w pierwszym przebiegu zaznaczamy potomkow
void mark1(int u, int c) {
    color[u] = c ;
    FOREACH(it, G1[u])
        mark1(*it, c) ;
}

// w drugim przebiegu liczymy ile potomkow zostalo zaznaczonych
int mark2(int u, int c) {
    int ret = (color[u]==c) ;
    FOREACH(it, G2[u])
        ret += mark2(*it, c) ;
    return ret ;
}

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
    for(int i=1 ; i<=n ; i++) {
        mark1(i, i) ;
        cout << mark2(i, i)-1 << " " ;
    }
    cout << endl ;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9616 KB Output is correct
2 Correct 7 ms 9600 KB Output is correct
3 Correct 6 ms 9656 KB Output is correct
4 Correct 6 ms 9676 KB Output is correct
5 Correct 6 ms 9676 KB Output is correct
6 Correct 6 ms 9624 KB Output is correct
7 Correct 6 ms 9676 KB Output is correct
8 Correct 15 ms 9676 KB Output is correct
9 Correct 15 ms 9676 KB Output is correct
10 Correct 18 ms 9792 KB Output is correct
11 Correct 8 ms 9676 KB Output is correct
12 Correct 21 ms 9804 KB Output is correct
13 Correct 20 ms 9808 KB Output is correct
14 Correct 21 ms 9804 KB Output is correct
15 Correct 40 ms 9804 KB Output is correct
16 Correct 46 ms 9844 KB Output is correct
17 Correct 67 ms 9860 KB Output is correct
18 Correct 10 ms 9804 KB Output is correct
19 Correct 67 ms 9804 KB Output is correct
20 Correct 68 ms 9888 KB Output is correct
21 Correct 70 ms 9888 KB Output is correct

Subtask #2
0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9616 KB Output is correct
2 Correct 7 ms 9600 KB Output is correct
3 Correct 6 ms 9656 KB Output is correct
4 Correct 6 ms 9676 KB Output is correct
5 Correct 6 ms 9676 KB Output is correct
6 Correct 6 ms 9624 KB Output is correct
7 Correct 6 ms 9676 KB Output is correct
8 Correct 15 ms 9676 KB Output is correct
9 Correct 15 ms 9676 KB Output is correct
10 Correct 18 ms 9792 KB Output is correct
11 Correct 8 ms 9676 KB Output is correct
12 Correct 21 ms 9804 KB Output is correct
13 Correct 20 ms 9808 KB Output is correct
14 Correct 21 ms 9804 KB Output is correct
15 Correct 40 ms 9804 KB Output is correct
16 Correct 46 ms 9844 KB Output is correct
17 Correct 67 ms 9860 KB Output is correct
18 Correct 10 ms 9804 KB Output is correct
19 Correct 67 ms 9804 KB Output is correct
20 Correct 68 ms 9888 KB Output is correct
21 Correct 70 ms 9888 KB Output is correct
22 Execution timed out 1092 ms 14532 KB Time limit exceeded
23 Halted 0 ms 0 KB -