Submission #1095288

#TimeUsernameProblemLanguageResultExecution timeMemory
1095288andrewpPaths (BOI18_paths)C++14
0 / 100
126 ms31236 KiB
//Dedicated to my love, ivaziva #pragma GCC optimize("Ofast") #include <bits/stdc++.h> using namespace std; #define int long long using pii = pair<int, int>; using ll = int64_t; #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend() #define dbg(x) cerr<<#x<<": "<<x<<'\n'; #define dbga(A,l_,r_){for(int i_=l_;i_<=r_;i_++)cerr<<A[i_]<<' ';cerr<<'\n';} #define dbgv(a_){for(auto x_:a_) cerr<<x_<<' ';cerr<<'\n';} const int N = 3e5 + 20; int n, m, k, a[N], ans1, ans2; vector<int> g[N]; bool was[N]; void dfs(int x) { was[x] = true; int f = 0, s = 0, t = 0; for (int u : g[x]) { if (a[u] == 1) { f++; } else if (a[u] == 2) { s++; } else { t++; } if (!was[u]) { dfs(u); } } if (a[x] == 1) { ans1 += 2 * (s * t); ans2 += s; ans2 += t; } else if (a[x] == 2) { ans1 += 2 * (f * t); ans2 += f; ans2 += t; } else { ans1 += 2 * (f * s); ans2 += f; ans2 += s; } } int32_t main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); cerr.tie(nullptr); cin >> n >> m >> k; for (int i = 1; i <= n; i++) { cin >> a[i]; was[i] = false; } for (int i = 0; i < m; i++) { int u, v; cin >> u >> v; g[u].push_back(v); g[v].push_back(u); } ans1 = 0, ans2 = 0; dfs(1); if (k == 1) { cout << 0 << '\n'; } else if (k == 2) { cout << ans1 << '\n'; } else if (k == 3) { cout << ans1 + ans2 << '\n'; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...