oj.uz

Submission #169251

# Submission time Handle Problem Language Result Execution time Memory
169251 2019-12-19T09:33:35 Z arnold518 Paths (BOI18_paths) C++14
100 / 100
 1871 ms 704472 KB 
#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

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.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 587 ms 571000 KB Output is correct
2 Correct 520 ms 571092 KB Output is correct
3 Correct 520 ms 571132 KB Output is correct
4 Correct 521 ms 571052 KB Output is correct
5 Correct 521 ms 571128 KB Output is correct
6 Correct 518 ms 571128 KB Output is correct
7 Correct 519 ms 571256 KB Output is correct
8 Correct 523 ms 571000 KB Output is correct
9 Correct 524 ms 571024 KB Output is correct
10 Correct 551 ms 571000 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 685 ms 588236 KB Output is correct
2 Correct 628 ms 584396 KB Output is correct
3 Correct 1357 ms 641604 KB Output is correct
4 Correct 708 ms 584440 KB Output is correct
5 Correct 651 ms 579724 KB Output is correct
6 Correct 1109 ms 626408 KB Output is correct
7 Correct 1383 ms 641484 KB Output is correct
8 Correct 1290 ms 645236 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 587 ms 571000 KB Output is correct
2 Correct 520 ms 571092 KB Output is correct
3 Correct 520 ms 571132 KB Output is correct
4 Correct 521 ms 571052 KB Output is correct
5 Correct 521 ms 571128 KB Output is correct
6 Correct 518 ms 571128 KB Output is correct
7 Correct 519 ms 571256 KB Output is correct
8 Correct 523 ms 571000 KB Output is correct
9 Correct 524 ms 571024 KB Output is correct
10 Correct 551 ms 571000 KB Output is correct
11 Correct 685 ms 588236 KB Output is correct
12 Correct 628 ms 584396 KB Output is correct
13 Correct 1357 ms 641604 KB Output is correct
14 Correct 708 ms 584440 KB Output is correct
15 Correct 651 ms 579724 KB Output is correct
16 Correct 1109 ms 626408 KB Output is correct
17 Correct 1383 ms 641484 KB Output is correct
18 Correct 1290 ms 645236 KB Output is correct
19 Correct 690 ms 588364 KB Output is correct
20 Correct 636 ms 584372 KB Output is correct
21 Correct 1331 ms 641552 KB Output is correct
22 Correct 762 ms 584564 KB Output is correct
23 Correct 667 ms 579752 KB Output is correct
24 Correct 1129 ms 626276 KB Output is correct
25 Correct 1350 ms 641668 KB Output is correct
26 Correct 1311 ms 645360 KB Output is correct
27 Correct 735 ms 598404 KB Output is correct
28 Correct 889 ms 602704 KB Output is correct
29 Correct 1871 ms 704472 KB Output is correct
30 Correct 1590 ms 657284 KB Output is correct
31 Correct 1703 ms 663528 KB Output is correct
32 Correct 1822 ms 704396 KB Output is correct
33 Correct 518 ms 571076 KB Output is correct
34 Correct 594 ms 571060 KB Output is correct
35 Correct 523 ms 571128 KB Output is correct
36 Correct 520 ms 571128 KB Output is correct
37 Correct 516 ms 571132 KB Output is correct
38 Correct 520 ms 571004 KB Output is correct
39 Correct 524 ms 571144 KB Output is correct
40 Correct 540 ms 571192 KB Output is correct
41 Correct 522 ms 571000 KB Output is correct
42 Correct 521 ms 571312 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 517 ms 571000 KB Output is correct
2 Correct 630 ms 588276 KB Output is correct
3 Correct 571 ms 576944 KB Output is correct
4 Correct 756 ms 594424 KB Output is correct
5 Correct 663 ms 594404 KB Output is correct
6 Correct 1171 ms 657428 KB Output is correct
7 Correct 581 ms 579448 KB Output is correct
8 Correct 921 ms 615396 KB Output is correct
9 Correct 772 ms 613028 KB Output is correct
10 Correct 912 ms 624208 KB Output is correct
11 Correct 998 ms 624680 KB Output is correct
12 Correct 1020 ms 649040 KB Output is correct
13 Correct 1064 ms 631136 KB Output is correct
14 Correct 1241 ms 657576 KB Output is correct
15 Correct 1123 ms 659808 KB Output is correct
16 Correct 519 ms 571288 KB Output is correct
17 Correct 519 ms 571020 KB Output is correct
18 Correct 561 ms 571132 KB Output is correct
19 Correct 517 ms 570996 KB Output is correct
20 Correct 521 ms 571192 KB Output is correct
21 Correct 522 ms 571000 KB Output is correct
22 Correct 523 ms 571112 KB Output is correct
23 Correct 522 ms 571000 KB Output is correct
24 Correct 547 ms 570972 KB Output is correct
25 Correct 523 ms 570944 KB Output is correct