Submission #1147474

#	Time	Username	Problem	Language	Result	Execution time	Memory
1147474		sinataghizadeh	Paths (BOI18_paths)	C++20	100 / 100	699 ms	401444 KiB

paths

#include <bits/stdc++.h>
using namespace std;

typedef long long       ll;
typedef pair<int, int>  pii;
typedef pair<ll, ll>  pll;
#define all(x)                  (x).begin(),(x).end()
#define pb                      push_back
#define fi              first
#define se              second
#define beg             begin
#define siz              size()
#define fastio          cin.tie(NULL); cout.tie(NULL); ios_base::sync_with_stdio(false);
#define endl                    '\n'
#define ins             insert
#define log             LOG
const ll inf = 1e18;
const int maxn=3e5+2222;
ll n,m,k,col[maxn],dp[maxn][9][9],ans,d[maxn][9][9];
vector<ll>g[maxn];
int main() {
        cin>>n>>m>>k;
        for(int i=1;i<=n;i++)cin>>col[i];
        for(int i=1;i<=m;i++){
                ll u,v;cin>>u>>v;
                g[u].pb(v);g[v].pb(u);
        }
        for(int v=1;v<=n;v++){
                for(auto u:g[v]){
                        if(col[v]==col[u])continue;
                        dp[v][2][col[u]]++;
                }
        }
        for(int v=1;v<=n;v++){
                for(auto u:g[v]){
                        if(col[v]==col[u])continue;
                        for(int a=1;a<=k;a++){
                                if(a!=col[v]&&a!=col[u]){
                                        vector<ll>aa;
                                        for(int j=1;j<=5;j++){
                                                if(j!=a && j!=col[v]&&j!=col[u])aa.pb(j);
                                        }
                                        ll xx=aa[0],yy=aa[1];
                                        if(xx>yy)swap(xx,yy);
                                        d[v][xx][yy]+=dp[u][2][a];
                                }
                        }
                }
        }
        for(int v=1;v<=n;v++){
                for(auto u:g[v]){
                        for(int a=1;a<=5;a++){
                                //if(a==col[v] or a==col[u])continue;
                                ll xx=a,yy=col[v];
                                if(xx>yy)swap(xx,yy);
                                dp[v][4][a]+=d[u][xx][yy];
                        }
                }
        }
        for(int v=1;v<=n;v++){
                for(auto u:g[v]){
                        dp[v][5][0]+=dp[u][4][col[v]];
                }
        }
        for(int i=1;i<=n;i++){
                for(int j=0;j<=5;j++){
                        for(int a=0;a<=5;a++){
                                ans+=dp[i][j][a];
                        }
                }
        }
        for(int i=1;i<=n;i++){
                for(int j=1;j<=5;j++){
                        for(int a=j+1;a<=5;a++){
                                ans+=d[i][j][a];
                        }
                }
        }
        cout<<ans<<endl;
}

• Subtask 1: 23 / 23
• Subtask 2: 20 / 20
• Subtask 3: 27 / 27
• Subtask 4: 30 / 30