oj.uz

Submission #379902

# Submission time Handle Problem Language Result Execution time Memory
379902 2021-03-19T15:58:47 Z Fidisk Paths (BOI18_paths) C++14
100 / 100
 571 ms 131056 KB 
#include <bits/stdc++.h>
using namespace std;

#define oo 1e12
#define fi first
#define se second
#define sp(iiii) setprecision(iiii)
#define IO ios_base::sync_with_stdio(false); cin.tie(0)
#define ms(aaaa,xxxx) memset(aaaa,xxxx,sizeof(aaaa))
#define cntbit(xxxx) __builtin_popcount(xxxx)
#define getbit(xxxx,aaaa) ((xxxx>>(aaaa-1))&1)

typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<pair<int,int>,int> piii;
typedef pair<long long,long long> pll;
typedef pair<pair<long long,long long>,long long> plll;
typedef pair<pair<long long,long long>,pair<long long,long long>> pllll;
typedef pair<pair<long long,long long>,bool> pllb;

const ll base=361;
const ll mod=1e9+7;
const ld eps=1e-5;

ll n,m,k,i,j,l,ii,a[500009],f[500009][43],res,u,v;
vector<ll> g[500009],t[509];

int main(){
    IO;
    cin>>n>>m>>k;
    for (i=1;i<=n;i++) {
        cin>>a[i];
    }
    for (i=1;i<=m;i++) {
        cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    for (i=1;i<=n;i++) {
        f[i][(1<<(a[i]-1))]=1;
    }
    //cout<<(1<<k)<<'\n';
    for (i=1;i<(1<<k);i++) {
        t[cntbit(i)].push_back(i);
    }
    for (i=2;i<=k;i++) {
        for (j=0;j<t[i].size();j++) {
            //cout<<i<<' '<<t[i][j]<<'\n';
            for (l=1;l<=n;l++) {
                if ((t[i][j]&(1<<(a[l]-1)))!=0) {
                    for (ii=0;ii<g[l].size();ii++) {
                        //cout<<i<<' '<<l<<' '<<t[i][j]<<" - "<<g[l][ii]<<' '<<(t[i][j]^(1<<(a[l]-1)))<<'\n';
                        f[l][t[i][j]]+=f[g[l][ii]][t[i][j]^(1<<(a[l]-1))];
                    }
                }
            }
        }
    }
    for (i=0;i<(1<<k);i++) {
        if (cntbit(i)>=2) {
            for (j=1;j<=n;j++) {
                res+=f[j][i];
            }
        }
    }
    cout<<res<<'\n';
}

Compilation message

paths.cpp: In function 'int main()':
paths.cpp:49:19: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |         for (j=0;j<t[i].size();j++) {
      |                  ~^~~~~~~~~~~~
paths.cpp:53:33: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |                     for (ii=0;ii<g[l].size();ii++) {
      |                               ~~^~~~~~~~~~~~

Subtask #1
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 12140 KB Output is correct
2 Correct 9 ms 12140 KB Output is correct
3 Correct 10 ms 12164 KB Output is correct
4 Correct 9 ms 12164 KB Output is correct
5 Correct 8 ms 12140 KB Output is correct
6 Correct 9 ms 12140 KB Output is correct
7 Correct 9 ms 12140 KB Output is correct
8 Correct 9 ms 12140 KB Output is correct
9 Correct 9 ms 12140 KB Output is correct
10 Correct 9 ms 12140 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 23916 KB Output is correct
2 Correct 73 ms 21740 KB Output is correct
3 Correct 429 ms 130412 KB Output is correct
4 Correct 149 ms 34028 KB Output is correct
5 Correct 132 ms 34036 KB Output is correct
6 Correct 276 ms 93916 KB Output is correct
7 Correct 405 ms 130416 KB Output is correct
8 Correct 430 ms 131056 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 12140 KB Output is correct
2 Correct 9 ms 12140 KB Output is correct
3 Correct 10 ms 12164 KB Output is correct
4 Correct 9 ms 12164 KB Output is correct
5 Correct 8 ms 12140 KB Output is correct
6 Correct 9 ms 12140 KB Output is correct
7 Correct 9 ms 12140 KB Output is correct
8 Correct 9 ms 12140 KB Output is correct
9 Correct 9 ms 12140 KB Output is correct
10 Correct 9 ms 12140 KB Output is correct
11 Correct 94 ms 23916 KB Output is correct
12 Correct 73 ms 21740 KB Output is correct
13 Correct 429 ms 130412 KB Output is correct
14 Correct 149 ms 34028 KB Output is correct
15 Correct 132 ms 34036 KB Output is correct
16 Correct 276 ms 93916 KB Output is correct
17 Correct 405 ms 130416 KB Output is correct
18 Correct 430 ms 131056 KB Output is correct
19 Correct 89 ms 23916 KB Output is correct
20 Correct 75 ms 21740 KB Output is correct
21 Correct 407 ms 130528 KB Output is correct
22 Correct 165 ms 33900 KB Output is correct
23 Correct 128 ms 33900 KB Output is correct
24 Correct 276 ms 93916 KB Output is correct
25 Correct 400 ms 130412 KB Output is correct
26 Correct 417 ms 131052 KB Output is correct
27 Correct 82 ms 21764 KB Output is correct
28 Correct 115 ms 26348 KB Output is correct
29 Correct 563 ms 130524 KB Output is correct
30 Correct 389 ms 76556 KB Output is correct
31 Correct 388 ms 76640 KB Output is correct
32 Correct 571 ms 130544 KB Output is correct
33 Correct 9 ms 12140 KB Output is correct
34 Correct 9 ms 12284 KB Output is correct
35 Correct 10 ms 12288 KB Output is correct
36 Correct 9 ms 12140 KB Output is correct
37 Correct 10 ms 12140 KB Output is correct
38 Correct 9 ms 12140 KB Output is correct
39 Correct 9 ms 12140 KB Output is correct
40 Correct 9 ms 12180 KB Output is correct
41 Correct 9 ms 12140 KB Output is correct
42 Correct 10 ms 12140 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12140 KB Output is correct
2 Correct 39 ms 15212 KB Output is correct
3 Correct 30 ms 15212 KB Output is correct
4 Correct 110 ms 51564 KB Output is correct
5 Correct 99 ms 51808 KB Output is correct
6 Correct 257 ms 51436 KB Output is correct
7 Correct 32 ms 15212 KB Output is correct
8 Correct 167 ms 51436 KB Output is correct
9 Correct 137 ms 51944 KB Output is correct
10 Correct 149 ms 51552 KB Output is correct
11 Correct 146 ms 33128 KB Output is correct
12 Correct 156 ms 42332 KB Output is correct
13 Correct 156 ms 33244 KB Output is correct
14 Correct 254 ms 51500 KB Output is correct
15 Correct 281 ms 51564 KB Output is correct
16 Correct 10 ms 12140 KB Output is correct
17 Correct 10 ms 12180 KB Output is correct
18 Correct 9 ms 12140 KB Output is correct
19 Correct 10 ms 12140 KB Output is correct
20 Correct 9 ms 12164 KB Output is correct
21 Correct 9 ms 12140 KB Output is correct
22 Correct 9 ms 12140 KB Output is correct
23 Correct 9 ms 12140 KB Output is correct
24 Correct 9 ms 12140 KB Output is correct
25 Correct 8 ms 12140 KB Output is correct