Submission #1156776

#	Time	Username	Problem	Language	Result	Execution time	Memory
1156776		the_ZHER	Paths (BOI18_paths)	C++20	43 / 100	3095 ms	20912 KiB

paths

#include <bits/stdc++.h>
#define boost ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define int long long
using namespace std;
const int inf=1e17;
const int N=3e5+5;
const int N1=1e5+5;
const int N2=5e6+6;
const int mod=1e9+7;
const int k1=447;
struct edge{
    int d,in;
};
struct edge1{
    int l,r;
};
vector<int>v;
vector<int>v1[N];
vector<int>v2;
int dp[5][5];
int cnt[5];
int ans=0;
void dfs(int x,string s,int st){
    s[v[x]-1]='1';
    if(st==4){
       ans++;
       return; 
    }
    for(int i=0;i<v1[x].size();i++){
        if(s[v[v1[x][i]]-1]=='0'){
        dfs(v1[x][i],s,st+1);
        }
    }
}
signed main(){
boost;
    int n,m,k;
    cin>>n>>m>>k;
    v.push_back(0);
    for(int i=1;i<=n;i++){
        int x;
        cin>>x;
        v.push_back(x);
    }
    for(int i=1;i<=m;i++){
        int x,y;
        cin>>x>>y;
        v1[x].push_back(y);
        v1[y].push_back(x);
        if(k>=2&&v[x]!=v[y]){
            ans+=2;
        }
        dp[v[x]][v[y]]++;
        dp[v[y]][v[x]]++;
    }
    if(k>=3){
        for(int i=1;i<=n;i++){
            for(int j=0;j<v1[i].size();j++){
                cnt[v[v1[i][j]]]++;
            }
            int cnt1=v1[i].size();
            if(cnt1==1){
                cnt[1]=0;
                cnt[2]=0;
                cnt[3]=0;
                cnt[4]=0;
                continue;
            }
            for(int j=0;j<v1[i].size();j++){
                int x=v1[i][j];
                if(v[x]!=v[i]){
                    ans+=(cnt1-cnt[v[x]]-cnt[v[i]])*2;
                }
                cnt1--;
                cnt[v[x]]--;
            }
            cnt[1]=0;
            cnt[2]=0;
            cnt[3]=0;
            cnt[4]=0;
        }
    }
if(k>=4){
    for(int i=1;i<=n;i++){
        dfs(i,"0000",1ll);
    }
}
    cout<<ans;
}  

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