oj.uz

Submission #374480

# Submission time Handle Problem Language Result Execution time Memory
374480 2021-03-07T10:27:17 Z kartel Svjetlo (COCI20_svjetlo) C++14
0 / 110
 281 ms 31660 KB 
#include <bits/stdc++.h>
#define in(x) freopen(x, "r", stdin)
#define out(x) freopen(x, "w", stdout)
//#include <time.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("-O3")
#define F first
#define S second
#define pb push_back
//#define M ll(1e9 + 7)
#define M ll(998244353)
#define sz(x) (int)x.size()
#define re return
#define oo ll(1e18)
#define el '\n'
#define pii pair <int, int>
#define all(x) (x).begin(), (x).end()
#define arr_all(x, n) (x + 1), (x + 1 + n)
#define vi vector<int>
#define eps (ld)1e-9
using namespace std;
typedef long long ll;
//using namespace __gnu_pbds;
//typedef tree <ll, null_type, less_equal <ll> , rb_tree_tag, tree_order_statistics_node_update> ordered_set;
typedef double ld;
typedef unsigned long long ull;
typedef short int si;

const int N = 5e5 + 500;

int ans, n;

vector <int> g[N];

void dfs(int v, int pr) {
    int cnt = 0;

    for (auto u : g[v]) {
        if (u == pr) {
            continue;
        }

        cnt++;

        dfs(u, v);
    }
    if (cnt & 1) {
        return;
    }
    if (cnt > 0)
        ans += 3;
}

int main()
{
//    mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());;
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//	in("toys.in");
//	out("toys.out");
//    in("input.txt");
//    out("output.txt");
//    cerr.precision(9); cerr << fixed;

//    clock_t tStart = clock();
    string s;
    cin >> n;
    cin >> s;

    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;

        g[u].pb(v);
        g[v].pb(u);
    }

    ans = n - 1;

    dfs(1, -1);

    cout << ans;
}


/*

7
4 6 7 2 3 1 5
*/

Subtask #1
0 / 20.0

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

Subtask #2
0 / 30.0

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

Subtask #3
0 / 30.0

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

Subtask #4
0 / 30.0

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