oj.uz

Submission #429432

# Submission time Handle Problem Language Result Execution time Memory
429432 2021-06-15T23:26:46 Z Ozy Star Trek (CEOI20_startrek) C++17
23 / 100
 113 ms 12956 KB 
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define rep(i,a,b) for (lli i = (a); i <= (b); i++)
#define repa(i,a,b) for (lli i = (a); i >= (b); i--)
#define debug(a) cout << #a << " = " << a << endl
#define debugsl(a) cout << #a << " = " << a << ", "

#define MAX 100000
#define mod 1000000007
#define pe first
#define ga second

lli n,d,a,b,g,p;
lli arr[3][MAX+2];
vector<lli> hijos[MAX+2];
pair<lli,lli> total;

lli ini(lli pos, lli padre) {

    lli res = 1;
    for (auto h : hijos[pos]) {
        if (h == padre) continue;
        a = ini(h,pos);
        arr[a][pos]++;
        res *= a;
    }

    if (res == 0) {arr[2][pos] = 1; return 1;}
    else {arr[2][pos] = 0; return 0;}
}

void DFS(lli pos, lli padre,lli val) {

    lli act;
    arr[val][pos]++;

    if (arr[0][pos] > 0) g++;
    else p++;

    for (auto h : hijos[pos]){
        if (h == padre) continue;

        arr[arr[2][h]][pos]--;
        if (arr[0][pos] > 0) act = 1;
        else act = 0;
        arr[arr[2][h]][pos]++;

        DFS(h,pos,act);
    }

    arr[val][pos]--;
}

pair<lli,lli> resuelve(lli pos, lli padre) {

    pair<lli,lli> k,res;

    res = {0,0};

    for (auto h : hijos[pos]) {
        if (h == padre) continue;

        k = resuelve(h,pos);
        arr[arr[2][h]][pos]--;
        if (arr[0][pos] == 0) {
            res.ga += k.pe;
            res.pe += k.ga;
        }
        else {
            res.ga += k.pe;
            res.ga += k.ga;
        }
        arr[arr[2][h]][pos]++;

    }

    res.ga += p;
    if (arr[0][pos] > 0) res.ga += g;
    else res.pe += g;

    return res;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> d;
    rep(i,1,n-1) {
        cin >> a >> b;
        hijos[a].push_back(b);
        hijos[b].push_back(a);
    }

    a = ini(1,0);
    DFS(1,0,1);

    total = resuelve(1,0);
    cout << total.ga;

}

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2636 KB Output is correct
2 Incorrect 4 ms 2768 KB Output isn't correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2636 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 3 ms 2636 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 2 ms 2672 KB Output is correct
6 Correct 2 ms 2636 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 3 ms 2636 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 2 ms 2672 KB Output is correct
6 Correct 2 ms 2636 KB Output is correct
7 Correct 3 ms 2764 KB Output is correct
8 Correct 2 ms 2764 KB Output is correct
9 Correct 3 ms 2636 KB Output is correct
10 Correct 3 ms 2676 KB Output is correct
11 Correct 2 ms 2636 KB Output is correct

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 3 ms 2636 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 2 ms 2672 KB Output is correct
6 Correct 2 ms 2636 KB Output is correct
7 Correct 3 ms 2764 KB Output is correct
8 Correct 2 ms 2764 KB Output is correct
9 Correct 3 ms 2636 KB Output is correct
10 Correct 3 ms 2676 KB Output is correct
11 Correct 2 ms 2636 KB Output is correct
12 Incorrect 113 ms 12956 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 3 ms 2636 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 2 ms 2672 KB Output is correct
6 Correct 2 ms 2636 KB Output is correct
7 Correct 3 ms 2764 KB Output is correct
8 Correct 2 ms 2764 KB Output is correct
9 Correct 3 ms 2636 KB Output is correct
10 Correct 3 ms 2676 KB Output is correct
11 Correct 2 ms 2636 KB Output is correct
12 Correct 3 ms 2636 KB Output is correct
13 Incorrect 3 ms 2676 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 3 ms 2636 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 2 ms 2672 KB Output is correct
6 Correct 2 ms 2636 KB Output is correct
7 Correct 3 ms 2764 KB Output is correct
8 Correct 2 ms 2764 KB Output is correct
9 Correct 3 ms 2636 KB Output is correct
10 Correct 3 ms 2676 KB Output is correct
11 Correct 2 ms 2636 KB Output is correct
12 Incorrect 113 ms 12956 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #8
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2636 KB Output is correct
2 Incorrect 4 ms 2768 KB Output isn't correct