oj.uz

Submission #641685

# Submission time Handle Problem Language Result Execution time Memory
641685 2022-09-17T12:24:01 Z Itamar Star Trek (CEOI20_startrek) C++14
0 / 100
 2 ms 2644 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+2;
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;
            if (f[i][0].first != padre[i].first)
                dfs2(f[i][0].first, sum);

        }
        else if (ans[i] == 1) {

            for (pi fr : f[i]) {
                if (fr.first != padre[i].first)
                    dfs2(fr.first, sum + ans[i]);

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

        }
        else if (ans[i] == 1) {
            
            for (pi fr : f[i]) {
                if (fr.first != padre[i].first)
                    dfs2(fr.first, sum + ans[i]);
            }
        }
    }
}
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 1 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
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 Incorrect 1 ms 2644 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 Incorrect 1 ms 2644 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 Incorrect 1 ms 2644 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 Incorrect 1 ms 2644 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 Incorrect 1 ms 2644 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #8
0 / 15.0

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