Submission #641661

#	Time	Username	Problem	Language	Result	Execution time	Memory
641661		Itamar	Star Trek (CEOI20_startrek)	C++14	0 / 100	2 ms	2644 KiB

startrek

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) {
    int p = padre[i].first;
    padre[i].second = padre[padre[p].first].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;
    }
    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 %= 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 (stderr)

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
• Subtask 2: 0 / 7
• Subtask 3: 0 / 8
• Subtask 4: 0 / 15
• Subtask 5: 0 / 15
• Subtask 6: 0 / 20
• Subtask 7: 0 / 20
• Subtask 8: 0 / 15