Submission #88693

#	Time	Username	Problem	Language	Result	Execution time	Memory
88693		igzi	Paths (BOI18_paths)	C++17	100 / 100	801 ms	214644 KiB

paths

#include <bits/stdc++.h>
#define maxN 300003

using namespace std;

long long d[6][35][maxN],b[maxN],n,m,k,a,c,i,j,t,s,ans;
vector <int> adj[maxN];

int p[6]={1,2,4,8,16,32};

int main()
{
    std::ios_base::sync_with_stdio(false);
    cin>>n>>m>>k;
    for(i=0;i<n;i++){
        cin>>b[i];
        b[i]--;
        d[1][p[b[i]]][i]=1;
    }
    for(i=0;i<m;i++){
        cin>>a>>c;
        a--;
        c--;
        adj[a].push_back(c);
        adj[c].push_back(a);
    }
    for(i=2;i<=k;i++){
        for(j=0;j<n;j++){
            for(t=0;t<p[k];t++){
                if((t | p[b[j]])!=t) continue;
                for(s=0;s<adj[j].size();s++){
                    d[i][t][j]+=d[i-1][t-p[b[j]]][adj[j][s]];
                }
                //cout<<i<<" "<<t<<" "<<j<<" "<<d[i][t][j]<<endl;
            }
        }
    }
    for(i=2;i<=k;i++){
        for(j=0;j<n;j++){
            for(t=0;t<p[k];t++){
                ans+=d[i][t][j];
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}

Compilation message (stderr)

paths.cpp: In function 'int main()':
paths.cpp:31:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 for(s=0;s<adj[j].size();s++){
                         ~^~~~~~~~~~~~~~

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