Submission #1249384

#TimeUsernameProblemLanguageResultExecution timeMemory
1249384corvusPaths (BOI18_paths)C++20
0 / 100
31 ms11072 KiB
#include <bits/stdc++.h> using namespace std; #define all(c) begin(c), end(c) #define pb push_back using ll = long long; const ll N = 3e5 + 100 , LOG = 27; int k , n , m ; vector <int> color , edj[N]; set <string> res; char get(int c) { return char(c + '0'); } void dfs(int node , vector <bool> vis , string s) { if(vis[color[node]]) return; vis[color[node]] = 1; s.pb(get(node)); if(s.size() > 1) res.insert(s); for(auto to : edj[node]) dfs(to , vis , s); s.pop_back(); vis[color[node]] = 0; } int main(){ ios_base::sync_with_stdio(0); cin.tie(nullptr); ll tt = 1; // cin >> tt; while(tt--){ cin >> n >> m >> k ; color.assign(n + 1 , {}); for(int i = 1 ; i <= n ; i ++) cin >> color[i]; for(int i = 0 ; i < m ; i ++) { int u , v ; cin >> u >> v; edj[u].pb(v); edj[v].pb(u); } long long res = 0 ; if(k >= 2) { res = m * 2; for(int i = 1 ; i <= n ; i ++) for(auto to : edj[i]) res -= (to == i); } if(k >= 3) { res += (m - 1)*2; for(int i = 1 ; i <= n ; i ++) { long long cnt[k + 1] = {}; for(auto to : edj[i]) { cnt[to] ++ ; } for(int i = 1 ; i <= k ; i ++) res -= ((cnt[i] * (cnt[i] - 1)) / 2); } } cout << res << '\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...