oj.uz

Submission #641690

# Submission time Handle Problem Language Result Execution time Memory
641690 2022-09-17T12:39:46 Z Itamar Star Trek (CEOI20_startrek) C++14
38 / 100
 121 ms 16332 KB 
using namespace std;
#include <iostream>
#include <vector>
#define pi pair<int,int>
#define vi vector<int>
#define ll long long
#include <algorithm>
const int siz = 1e5;
vector<pi> f[siz];
pi padre[siz];
int ans[siz];
int h[siz];
bool ch[siz];
const ll m = 1e9 + 7;
bool t;
bool fun(pi p1, pi p2) {
    return p2.second < p1.second;
}
ll powe(ll a, ll b) {
    if (b == 0)
        return 1;
    ll ans = powe(a, b / 2);
    ans = (ans * ans) % m;
    if (b % 2) {
        ans = (ans * a) % m;
    }
    return ans;
}
bool dfs(int i) {
    
    for (int j = 0; j < f[i].size(); j++) {
        int fr = f[i][j].first;
        if (fr != padre[i].first) {
            padre[fr].first = i;
            h[fr] = h[i] + 1;
            f[i][j].second = !dfs(fr);
            ans[i] += f[i][j].second;
        }
    }
    sort(f[i].begin(), f[i].end(), fun);
    return (bool)ans[i];
}
void dfs1(int i) {
    if (i) {
        int p = padre[i].first;
        padre[i].second = padre[p].second;
        if (f[p][0].first != i) {
            padre[i].second |= f[p][0].second;
        }
        else if (f[p].size() > 1) {
            padre[i].second |= f[p][1].second;
        }
        padre[i].second = !padre[i].second;
    }
    for (pi fr : f[i]) {
        if(fr.first!=padre[i].first)
        dfs1(fr.first);
    }
    //ans[i] += padre[i].second;
}
void dfs2(int i, int sum) {
    if (t) {
        if (h[i] % 2) {
            //if (sum == (h[i] + 1) / 2)
            ch[i] = 1;
            
            for (pi fr : f[i]) {
                if (fr.first != padre[i].first)
                    dfs2(fr.first, sum + ans[i]);

            }

        }
        else if (ans[i] == 1) {
            if (f[i][0].first != padre[i].first)
                dfs2(f[i][0].first, sum);
           
        }
    }
    else {
        if (h[i] % 2==0) {
            //if (sum == (h[i] + 1) / 2)
                ch[i] = 1;
                

                for (pi fr : f[i]) {
                    if (fr.first != padre[i].first)
                        dfs2(fr.first, sum + ans[i]);
                }
        }
        else if (ans[i] == 1) {
            
            if (f[i][0].first != padre[i].first)
                dfs2(f[i][0].first, sum);
        }
    }
}
int main()
{
    ll n,d;
    cin >> n >> d;

    for (int i = 0; i < n-1; i++) {
        int a, b;
        cin >> a >> b;
        a--, b--;
        f[a].push_back({ b,0 });
        f[b].push_back({ a,0 });
    }
    dfs(0);
    dfs1(0);
    t = ans[0];
    dfs2(0,0);
    int sum = 0;
    for (int i = 0; i < n; i++) {
        ans[i] = ((bool)(ans[i])) || padre[i].second;
        sum += ans[i];
    }
    ll fin=0;
    sum = n - sum;
    if (ans[0]) {
        for (int i = 0; i < n; i++) {
            if (ch[i]) {
                fin += n-sum;
            }
            else {
                fin += n;
            }
        }
    }
    else {
        for (int i = 0; i < n; i++) {
            if (ch[i]) {
                fin += sum;
            }
        }
    }
    fin = fin%m;
    cout << fin;
}

// Run program: Ctrl + F5 or Debug > Start Without Debugging menu
// Debug program: F5 or Debug > Start Debugging menu

// Tips for Getting Started: 
//   1. Use the Solution Explorer window to add/manage files
//   2. Use the Team Explorer window to connect to source control
//   3. Use the Output window to see build output and other messages
//   4. Use the Error List window to view errors
//   5. Go to Project > Add New Item to create new code files, or Project > Add Existing Item to add existing code files to the project
//   6. In the future, to open this project again, go to File > Open > Project and select the .sln file

Compilation message

startrek.cpp: In function 'bool dfs(int)':
startrek.cpp:31:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |     for (int j = 0; j < f[i].size(); j++) {
      |                     ~~^~~~~~~~~~~~~

Subtask #1
0.0 / 0.0

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

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2644 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 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2656 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 3 ms 2644 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2656 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 3 ms 2644 KB Output is correct
7 Correct 2 ms 2644 KB Output is correct
8 Correct 2 ms 2760 KB Output is correct
9 Correct 2 ms 2664 KB Output is correct
10 Correct 3 ms 2644 KB Output is correct
11 Correct 3 ms 2644 KB Output is correct

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2656 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 3 ms 2644 KB Output is correct
7 Correct 2 ms 2644 KB Output is correct
8 Correct 2 ms 2760 KB Output is correct
9 Correct 2 ms 2664 KB Output is correct
10 Correct 3 ms 2644 KB Output is correct
11 Correct 3 ms 2644 KB Output is correct
12 Correct 107 ms 12276 KB Output is correct
13 Correct 110 ms 16332 KB Output is correct
14 Correct 93 ms 8720 KB Output is correct
15 Correct 96 ms 8932 KB Output is correct
16 Correct 121 ms 9060 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2656 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 3 ms 2644 KB Output is correct
7 Correct 2 ms 2644 KB Output is correct
8 Correct 2 ms 2760 KB Output is correct
9 Correct 2 ms 2664 KB Output is correct
10 Correct 3 ms 2644 KB Output is correct
11 Correct 3 ms 2644 KB Output is correct
12 Correct 2 ms 2644 KB Output is correct
13 Incorrect 3 ms 2644 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 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2656 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 3 ms 2644 KB Output is correct
7 Correct 2 ms 2644 KB Output is correct
8 Correct 2 ms 2760 KB Output is correct
9 Correct 2 ms 2664 KB Output is correct
10 Correct 3 ms 2644 KB Output is correct
11 Correct 3 ms 2644 KB Output is correct
12 Correct 107 ms 12276 KB Output is correct
13 Correct 110 ms 16332 KB Output is correct
14 Correct 93 ms 8720 KB Output is correct
15 Correct 96 ms 8932 KB Output is correct
16 Correct 121 ms 9060 KB Output is correct
17 Correct 2 ms 2644 KB Output is correct
18 Incorrect 3 ms 2644 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #8
0 / 15.0

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