Submission #1193361

#TimeUsernameProblemLanguageResultExecution timeMemory
1193361SSSMPaths (BOI18_paths)C++20
100 / 100
264 ms37568 KiB
#include <bits/stdc++.h> /* #pragma GCC optimize("O3") #pragma GCC optimize("Ofast") #pragma GCC target ("avx2") */ using namespace std; /* #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace __gnu_pbds; template<class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; */ #define F first #define S second #define pb push_back #define FIO freopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout) #define md(a) ((a%mod+mod)%mod) #define all(a) a.begin(), a.end() #define MP make_pair #define lc (id<<1) #define rc (lc|1) #define mid (l+r)/2 #define kill(a) cout << a << "\n", exit(0) #define SZ(a) (ll)a.size() typedef pair<int,int> pii; typedef pair<long long ,long long> pll; typedef long long ll; typedef long double ld; typedef vector<vector<ll>> matrix; mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); ll const maxn=3e5+10, mod=1e9+7, INF=1e18, LOG=20, sq=65; ll poww(ll a, ll b, ll mod) { if (b == 0) return 1; return 1 * poww(1 * a * a % mod, b / 2, mod) * ((b % 2 == 1) ? a : 1) % mod; } ll n, m, k, ans, dp[maxn][6], col[maxn]; vector<ll> ver[6], g[maxn]; bool mark[6]; void bt(ll lst, ll len) { len++; for(ll c=1;c<=k;c++) if(!mark[c]){ mark[c]=1; for(ll i=1;i<=n;i++) dp[i][len]=0; for(ll v:ver[c]) { for(ll u:g[v]) if(col[u]==lst){ dp[v][len]+=dp[u][len-1]; } ans+=dp[v][len]; } bt(c, len); mark[c]=0; } } int main() { ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); cin>>n>>m>>k; for(ll i=1;i<=n;i++){ cin>>col[i]; ver[col[i]].pb(i); } for(ll i=1;i<=m;i++) { ll v, u; cin>>v>>u; g[v].pb(u); g[u].pb(v); } for(ll i=1;i<=k;i++) { mark[i]=1; for(ll v:ver[i]) dp[v][1]=1; bt(i, 1); mark[i]=0; } cout<<ans<<"\n"; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...