Submission #645472

#TimeUsernameProblemLanguageResultExecution timeMemory
645472mychecksedadPaths (BOI18_paths)C++17
23 / 100
69 ms28092 KiB
/* Author : Mychecksdead */ #include<bits/stdc++.h> using namespace std; typedef long long int ll; typedef long double ld; #define MOD (1000000000+7) #define MOD1 (998244353) #define PI 3.1415926535 #define pb push_back #define setp() cout << setprecision(15) #define all(x) x.begin(), x.end() #define debug(x) cerr << #x << " is " << x << '\n'; const int N = 1e6+100, M = 1e5+10, F = 2147483646, K = 20; int n, m, k, a[N]; ll ans = 0, dp[N][3]; vector<int> g[N]; vector<bool> vis(N); void dfs(int v, int p){ vis[v] = 1; if(a[v] == 0) ans += dp[v][1] * dp[v][2]; else if(a[v] == 1) ans += dp[v][0] * dp[v][2]; else if(a[v] == 2) ans += dp[v][0] * dp[v][1]; for(int u: g[v]){ if(u != p){ int mask = (1<<a[v]) + (1<<a[u]); if(a[v] != a[u]){ ans++; if(mask == 3) ans += dp[u][2]; if(mask == 5) ans += dp[u][1]; if(mask == 6) ans += dp[u][0]; } if(vis[u]) continue; dp[u][a[v]]--; dfs(u, v); dp[u][a[v]]++; } } } void dfs1(int v, int p, int d, vector<int> &x){ if(d>1){ ans++; } for(int u: g[v]){ if(u != p){ if(x[a[u]]) continue; x[a[u]] = 1; dfs1(u, v, d + 1, x); x[a[u]] = 0; } } } void solve(){ cin >> n >> m >> k; for(int i = 1; i <= n; ++i) cin >> a[i]; for(int i = 1; i <= n; ++i) --a[i], dp[i][0] = dp[i][1] = dp[i][2] = 0; for(int i = 0; i < m; ++i){ int u, v; cin >> u >> v; g[u].pb(v); g[v].pb(u); dp[u][a[v]]++; dp[v][a[u]]++; } if(n <= 100){ vector<int> v (4); for(int i = 1; i <= n; ++i){ v[0] = v[1] = v[2] = v[3] = 0; v[a[i]] = 1; dfs1(i, 0, 1, v); } }else{ for(int i = 1; i <= n; ++i) if(!vis[i]) dfs(i, 0); ans *= 2; } cout << ans; } int main(){ cin.tie(0); ios::sync_with_stdio(0); int T = 1, aa; // cin >> T;aa=T; while(T--){ // cout << "Case #" << aa-T << ": "; solve(); cout << '\n'; } return 0; }

Compilation message (stderr)

paths.cpp: In function 'int main()':
paths.cpp:91:16: warning: unused variable 'aa' [-Wunused-variable]
   91 |     int T = 1, aa;
      |                ^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...