oj.uz

답안 #427828

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
427828 2021-06-15T00:33:28 Z Ozy Star Trek (CEOI20_startrek) C++17
0 / 100
 6 ms 5196 KB 
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define rep(i,a,b) for(int i = (a); i <= (b); i++)
#define repa(i,a,b) for(int i = (a); i >= (b); i--)
#define debugsl(a) cout << #a << " = " << a << ", "
#define debug(a) cout << #a << " = " << a << endl;

#define MAX 100000
#define mod 1000000007

bool si;
lli n,d,a,b,total,g,p;
vector<lli> hijos[MAX+2];
lli estado[MAX+2],original[MAX+2];

lli DFS (lli pos, lli padre) {
    lli res = 1;
    lli cant = 0;
    for (auto h : hijos[pos]) {
        if (h == padre) continue;
        cant++;
        res *= DFS(h,pos);
    }

    if (cant == 0) {
        if (si) original[pos] = 0;
        return 0;
    }

    if (res == 0) {
        if (si) original[pos] = 1;
        return 1;
    }
    else {
        if (si) original[pos] = 0;
        return 0;
    }
}

lli  resuelve(lli pos, lli padre, lli prof) {

    if (prof%2 == 0) total += p;
    else if (original[pos] == 0) total += g;
    if (total > mod) total %= mod;

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

        if (prof%2 == 0){
            if (original[pos] == 0) {
                if (hijos[pos].size() <= 2) resuelve(h,pos,prof+1);
            }
            else if (original[h] == 0) resuelve(h,pos,prof+1);
        }
        else {
            if (original[pos] == 1) {
                if (hijos[pos].size() <= 2) resuelve(h,pos,prof+1);
            }
            else resuelve(h,pos,prof+1);
        }
    }
}

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);
    }

    si = true;
    rep(i,1,n) {
        estado[i] = DFS(i,0);

        si = false;
        if (estado[i] == 0) p++;
        else g++;
    }

    total = 0;
    resuelve(1,0,0);

    cout << total;
    
    return 0;
}

Compilation message

startrek.cpp: In function 'long long int resuelve(long long int, long long int, long long int)':
startrek.cpp:64:1: warning: no return statement in function returning non-void [-Wreturn-type]
   64 | }
      | ^

Subtask #1
0 / 0.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 6 ms 5184 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 5 ms 5196 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 5 ms 5168 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 5 ms 5168 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 5 ms 5168 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 5 ms 5168 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 5 ms 5168 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #8
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 6 ms 5184 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -