oj.uz

Submission #98723

# Submission time Handle Problem Language Result Execution time Memory
98723 2019-02-25T11:56:17 Z onjo0127 Paths (BOI18_paths) C++11
73 / 100
 3000 ms 27356 KB 
#include <bits/stdc++.h>
using namespace std;

vector<int> adj[300009];
int C[300009], D[300009][5];

int main() {
    long long a2 = 0, a3 = 0, a4 = 0, a5 = 0;
    int N, M, K; scanf("%d%d%d",&N,&M,&K);
    for(int i=1; i<=N; i++) {scanf("%d",&C[i]); --C[i];}
    for(int i=0; i<M; i++) {
        int u, v; scanf("%d%d",&u,&v);
        if(C[u] != C[v]) a2 += 2;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    for(int i=1; i<=N; i++) for(auto& it: adj[i]) ++D[i][C[it]];
    for(int i=1; i<=N; i++) {
        for(int a=0; a<5; a++) for(int b=0; b<5; b++) if(a != b && C[i] != a && C[i] != b) a3 += 1LL * D[i][a] * D[i][b];
        for(auto& it: adj[i]) {
            if(C[i] == C[it]) continue;
            for(int a=0; a<5; a++) {
                for(int b=0; b<5; b++) {
                    set<int> st = {C[i], C[it], a, b};
                    if((int)st.size() == 4) a4 += 1LL * D[i][a] * D[it][b];
                }
            }
        }
      	if(K == 5) {
          vector<int> S;
          for(int a=0; a<5; a++) if(a != C[i]) S.push_back(a);
          do {
              long long a = 0, b = 0;
              for(auto& it: adj[i]) if(C[it] == S[0]) a += D[it][S[1]];
              for(auto& it: adj[i]) if(C[it] == S[2]) b += D[it][S[3]];
              a4 += a * b;
          } while(next_permutation(S.begin(), S.end()));
        }
    }
    printf("%lld", a2 + a3 + a4 + a5);
    return 0;
}

Compilation message

paths.cpp: In function 'int main()':
paths.cpp:9:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     int N, M, K; scanf("%d%d%d",&N,&M,&K);
                  ~~~~~^~~~~~~~~~~~~~~~~~~
paths.cpp:10:35: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i=1; i<=N; i++) {scanf("%d",&C[i]); --C[i];}
                              ~~~~~^~~~~~~~~~~~
paths.cpp:12:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         int u, v; scanf("%d%d",&u,&v);
                   ~~~~~^~~~~~~~~~~~~~

Subtask #1
23.0 / 23.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1876 ms 11168 KB Output is correct
2 Correct 1876 ms 11000 KB Output is correct
3 Correct 2737 ms 22828 KB Output is correct
4 Correct 1572 ms 12484 KB Output is correct
5 Correct 162 ms 12536 KB Output is correct
6 Correct 2199 ms 19304 KB Output is correct
7 Correct 2435 ms 22912 KB Output is correct
8 Correct 2281 ms 23372 KB Output is correct

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7424 KB Output is correct
2 Correct 9 ms 7424 KB Output is correct
3 Correct 10 ms 7424 KB Output is correct
4 Correct 11 ms 7424 KB Output is correct
5 Correct 8 ms 7424 KB Output is correct
6 Correct 9 ms 7424 KB Output is correct
7 Correct 9 ms 7424 KB Output is correct
8 Correct 9 ms 7424 KB Output is correct
9 Correct 10 ms 7424 KB Output is correct
10 Correct 9 ms 7424 KB Output is correct
11 Correct 1876 ms 11168 KB Output is correct
12 Correct 1876 ms 11000 KB Output is correct
13 Correct 2737 ms 22828 KB Output is correct
14 Correct 1572 ms 12484 KB Output is correct
15 Correct 162 ms 12536 KB Output is correct
16 Correct 2199 ms 19304 KB Output is correct
17 Correct 2435 ms 22912 KB Output is correct
18 Correct 2281 ms 23372 KB Output is correct
19 Correct 1902 ms 11176 KB Output is correct
20 Correct 1812 ms 10952 KB Output is correct
21 Correct 2403 ms 22776 KB Output is correct
22 Correct 1810 ms 12664 KB Output is correct
23 Correct 193 ms 12592 KB Output is correct
24 Correct 2152 ms 19180 KB Output is correct
25 Correct 2244 ms 22780 KB Output is correct
26 Correct 2286 ms 23548 KB Output is correct
27 Correct 2011 ms 11000 KB Output is correct
28 Correct 2328 ms 12256 KB Output is correct
29 Correct 2717 ms 22904 KB Output is correct
30 Correct 2573 ms 16744 KB Output is correct
31 Correct 2759 ms 16868 KB Output is correct
32 Execution timed out 3014 ms 27356 KB Time limit exceeded
33 Halted 0 ms 0 KB -

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7464 KB Output is correct
2 Correct 866 ms 8484 KB Output is correct
3 Correct 626 ms 8472 KB Output is correct
4 Correct 833 ms 12556 KB Output is correct
5 Correct 982 ms 13296 KB Output is correct
6 Correct 1042 ms 12536 KB Output is correct
7 Correct 698 ms 8540 KB Output is correct
8 Correct 790 ms 12628 KB Output is correct
9 Correct 803 ms 13424 KB Output is correct
10 Correct 1000 ms 13420 KB Output is correct
11 Correct 781 ms 10356 KB Output is correct
12 Correct 1008 ms 12016 KB Output is correct
13 Correct 959 ms 10480 KB Output is correct
14 Correct 1016 ms 12664 KB Output is correct
15 Correct 919 ms 12792 KB Output is correct
16 Correct 9 ms 7424 KB Output is correct
17 Correct 9 ms 7424 KB Output is correct
18 Correct 11 ms 7424 KB Output is correct
19 Correct 10 ms 7424 KB Output is correct
20 Correct 9 ms 7424 KB Output is correct
21 Correct 10 ms 7424 KB Output is correct
22 Correct 10 ms 7424 KB Output is correct
23 Correct 10 ms 7424 KB Output is correct
24 Correct 10 ms 7424 KB Output is correct
25 Correct 8 ms 7424 KB Output is correct