Submission #169251

#	Time	Username	Problem	Language	Result	Execution time	Memory
169251		arnold518	Paths (BOI18_paths)	C++14	100 / 100	1871 ms	704472 KiB

paths

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

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 3e5;
const int MAXK = 5;

int N, M, K, KK, A[MAXN+10];
vector<int> adj[MAXN+10], adj2[MAXN*40+10], revadj2[MAXN*40+10];
ll dp[MAXN*40+10], ans;

vector<int> S;
bool vis[MAXN*40+10];
void dfs(int now)
{
    vis[now]=true;
    for(int nxt : adj2[now])
    {
        if(vis[nxt]) continue;
        dfs(nxt);
    }
    S.push_back(now);
}

int main()
{
    int i, j, k;

    scanf("%d%d%d", &N, &M, &K); KK=(1<<K);
    for(i=1; i<=N; i++) scanf("%d", &A[i]), A[i]--;
    for(i=1; i<=M; i++)
    {
        int u, v;
        scanf("%d%d", &u, &v);
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    for(i=1; i<=N; i++) for(j=0; j<(1<<K); j++)
    {
        if((j&(1<<A[i]))==0) continue;
        int now=(i<<K)+j;
        for(auto to : adj[i])
        {
            if(j&(1<<A[to])) continue;
            int nxt=(to<<K)+(j|(1<<A[to]));
            adj2[now].push_back(nxt);
            revadj2[nxt].push_back(now);
/*
            printf("%d ", now>>K);
            for(k=0; k<K; k++) printf("%d", (bool)(now&(1<<k)));

            printf(" / ");

            printf("%d ", nxt>>K);
            for(k=0; k<K; k++) printf("%d", (bool)(nxt&(1<<k)));
            printf("\n");*/
        }
    }

    for(i=1; i<=N; i++) dfs((i<<K)+(1<<A[i]));
    reverse(S.begin(), S.end());

    for(auto now : S)
    {
        if(now==((now>>K)<<K)+(1<<A[now>>K])) dp[now]=1;
        for(auto nxt : revadj2[now]) dp[now]+=dp[nxt];
        ans+=dp[now];
    }

    ans-=N;
    printf("%lld", ans);
}

Compilation message (stderr)

paths.cpp: In function 'int main()':
paths.cpp:30:15: warning: unused variable 'k' [-Wunused-variable]
     int i, j, k;
               ^
paths.cpp:32:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d", &N, &M, &K); KK=(1<<K);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~
paths.cpp:33:43: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(i=1; i<=N; i++) scanf("%d", &A[i]), A[i]--;
                         ~~~~~~~~~~~~~~~~~~^~~~~~~~
paths.cpp:37:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &u, &v);
         ~~~~~^~~~~~~~~~~~~~~~

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