oj.uz

Submission #418112

# Submission time Handle Problem Language Result Execution time Memory
418112 2021-06-05T06:06:45 Z juggernaut Paths (BOI18_paths) C++17
100 / 100
 563 ms 97100 KB 
#include<bits/stdc++.h>
#define fr first
#define sc second
using namespace std;
void usaco(string s){freopen((s+".in").c_str(),"r",stdin);freopen((s+".out").c_str(),"w",stdout);}
typedef long long ll;
#define USING_ORDERED_SET 0
#if USING_ORDERED_SET
#include<bits/extc++.h>
using namespace __gnu_pbds;
template<class T>using ordered_set=tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
#endif
template<class T>void umax(T &a,T b){if(a<b)a=b;}
template<class T>void umin(T &a,T b){if(b<a)a=b;}
#ifdef IOI2021SG
    #define printl(args...)printf(args)
#else
    #define printl(args...)((void)0)
#endif
int n,m,k;
int a[300005];
vector<int>g[300005];
ll ans;
ll cnt[300005][32];
int main(){
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]),a[i]--;
    while(m--){
        int x,y;
        scanf("%d%d",&x,&y);
        g[x].push_back(y);
        g[y].push_back(x);
    }
    for(int mask=1;mask<(1<<k);mask++){
        for(int i=1;i<=n;i++){
            if(mask>>a[i]&1^1)continue;
            if(__builtin_popcount(mask)==1)cnt[i][mask]++;
            for(int to:g[i])if(a[i]!=a[to])cnt[i][mask]+=cnt[to][mask^(1<<a[i])];
            ans+=cnt[i][mask];
        }
    }
    printf("%lld",ans-n);
}

Compilation message

paths.cpp: In function 'int main()':
paths.cpp:36:26: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   36 |             if(mask>>a[i]&1^1)continue;
      |                ~~~~~~~~~~^~
paths.cpp: In function 'void usaco(std::string)':
paths.cpp:5:29: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    5 | void usaco(string s){freopen((s+".in").c_str(),"r",stdin);freopen((s+".out").c_str(),"w",stdout);}
      |                      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
paths.cpp:5:66: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    5 | void usaco(string s){freopen((s+".in").c_str(),"r",stdin);freopen((s+".out").c_str(),"w",stdout);}
      |                                                           ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
paths.cpp: In function 'int main()':
paths.cpp:26:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |     scanf("%d%d%d",&n,&m,&k);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~
paths.cpp:27:31: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |     for(int i=1;i<=n;i++)scanf("%d",&a[i]),a[i]--;
      |                          ~~~~~^~~~~~~~~~~~
paths.cpp:30:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |         scanf("%d%d",&x,&y);
      |         ~~~~~^~~~~~~~~~~~~~

Subtask #1
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7244 KB Output is correct
2 Correct 4 ms 7372 KB Output is correct
3 Correct 4 ms 7252 KB Output is correct
4 Correct 4 ms 7244 KB Output is correct
5 Correct 5 ms 7372 KB Output is correct
6 Correct 4 ms 7316 KB Output is correct
7 Correct 4 ms 7244 KB Output is correct
8 Correct 4 ms 7372 KB Output is correct
9 Correct 4 ms 7244 KB Output is correct
10 Correct 4 ms 7268 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 12232 KB Output is correct
2 Correct 81 ms 11080 KB Output is correct
3 Correct 419 ms 91980 KB Output is correct
4 Correct 130 ms 19392 KB Output is correct
5 Correct 114 ms 19320 KB Output is correct
6 Correct 291 ms 65300 KB Output is correct
7 Correct 402 ms 91940 KB Output is correct
8 Correct 421 ms 92820 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7244 KB Output is correct
2 Correct 4 ms 7372 KB Output is correct
3 Correct 4 ms 7252 KB Output is correct
4 Correct 4 ms 7244 KB Output is correct
5 Correct 5 ms 7372 KB Output is correct
6 Correct 4 ms 7316 KB Output is correct
7 Correct 4 ms 7244 KB Output is correct
8 Correct 4 ms 7372 KB Output is correct
9 Correct 4 ms 7244 KB Output is correct
10 Correct 4 ms 7268 KB Output is correct
11 Correct 93 ms 12232 KB Output is correct
12 Correct 81 ms 11080 KB Output is correct
13 Correct 419 ms 91980 KB Output is correct
14 Correct 130 ms 19392 KB Output is correct
15 Correct 114 ms 19320 KB Output is correct
16 Correct 291 ms 65300 KB Output is correct
17 Correct 402 ms 91940 KB Output is correct
18 Correct 421 ms 92820 KB Output is correct
19 Correct 98 ms 15024 KB Output is correct
20 Correct 85 ms 13380 KB Output is correct
21 Correct 410 ms 96604 KB Output is correct
22 Correct 127 ms 22724 KB Output is correct
23 Correct 114 ms 22724 KB Output is correct
24 Correct 290 ms 69440 KB Output is correct
25 Correct 410 ms 96396 KB Output is correct
26 Correct 411 ms 97100 KB Output is correct
27 Correct 88 ms 13328 KB Output is correct
28 Correct 113 ms 16536 KB Output is correct
29 Correct 563 ms 96460 KB Output is correct
30 Correct 337 ms 55376 KB Output is correct
31 Correct 369 ms 55376 KB Output is correct
32 Correct 551 ms 96452 KB Output is correct
33 Correct 5 ms 7352 KB Output is correct
34 Correct 5 ms 7348 KB Output is correct
35 Correct 4 ms 7372 KB Output is correct
36 Correct 5 ms 7356 KB Output is correct
37 Correct 4 ms 7372 KB Output is correct
38 Correct 4 ms 7372 KB Output is correct
39 Correct 5 ms 7372 KB Output is correct
40 Correct 5 ms 7372 KB Output is correct
41 Correct 5 ms 7308 KB Output is correct
42 Correct 4 ms 7244 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7244 KB Output is correct
2 Correct 36 ms 8468 KB Output is correct
3 Correct 30 ms 9268 KB Output is correct
4 Correct 113 ms 36908 KB Output is correct
5 Correct 96 ms 37692 KB Output is correct
6 Correct 231 ms 36900 KB Output is correct
7 Correct 33 ms 9300 KB Output is correct
8 Correct 153 ms 36800 KB Output is correct
9 Correct 130 ms 37668 KB Output is correct
10 Correct 152 ms 37488 KB Output is correct
11 Correct 148 ms 23028 KB Output is correct
12 Correct 134 ms 30416 KB Output is correct
13 Correct 143 ms 23120 KB Output is correct
14 Correct 278 ms 36920 KB Output is correct
15 Correct 334 ms 36936 KB Output is correct
16 Correct 5 ms 7244 KB Output is correct
17 Correct 4 ms 7372 KB Output is correct
18 Correct 4 ms 7244 KB Output is correct
19 Correct 5 ms 7372 KB Output is correct
20 Correct 4 ms 7244 KB Output is correct
21 Correct 4 ms 7372 KB Output is correct
22 Correct 4 ms 7372 KB Output is correct
23 Correct 6 ms 7348 KB Output is correct
24 Correct 5 ms 7244 KB Output is correct
25 Correct 6 ms 7244 KB Output is correct