oj.uz

Submission #58711

# Submission time Handle Problem Language Result Execution time Memory
58711 2018-07-19T01:06:05 Z onjo0127(#1933) Paths (BOI18_paths) C++11
23 / 100
 508 ms 30220 KB 
#include <bits/stdc++.h>
using namespace std;

vector<int> adj[300009];
int color[300009], ans, cnt[300009][11];
bool vs[300009], c[11];

void go(int now, int lft) {
    ++ans;
    if(lft == 0) return;
    vs[now] = 1; c[color[now]] = 1;
    for(auto &it : adj[now]) {
        if(!vs[it] && !c[color[it]]) {
            go(it, lft - 1);
        }
    }
    vs[now] = 0; c[color[now]] = 0;
}

int main() {
    int N, M, K;
    scanf("%d%d%d",&N,&M,&K);
    for(int i=1; i<=N; i++) scanf("%d",&color[i]);
    for(int i=0; i<M; i++) {
        int u, v; scanf("%d%d",&u,&v);
        adj[u].push_back(v);
        adj[v].push_back(u);
        ++cnt[u][color[v]];
        ++cnt[v][color[u]];
    }
    if(K == 1) return !printf("0");
    if(N <= 100 && M <= 100 && K <= 4) {
        for(int i=1; i<=N; i++) go(i, K-1);
        printf("%d", ans - N);
    }
    else if(N <= 300000 && M <= 300000 && K <= 3) {
        int tmp = 1 ^ 2 ^ 3;
        for(int i=1; i<=N; i++) {
            for(auto &it : adj[i]) {
                if(color[i] != color[it]) {
                    ++ans;
                    if(K == 3) ans += cnt[it][tmp ^ color[i] ^ color[it]];
                }
            }
        }
        printf("%d", ans);
    }
    return 0;
}

Compilation message

paths.cpp: In function 'int main()':
paths.cpp:22: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);
     ~~~~~^~~~~~~~~~~~~~~~~~~
paths.cpp:23:34: 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",&color[i]);
                             ~~~~~^~~~~~~~~~~~~~~~
paths.cpp:25: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 7380 KB Output is correct
2 Correct 10 ms 7392 KB Output is correct
3 Correct 9 ms 7584 KB Output is correct
4 Correct 7 ms 7584 KB Output is correct
5 Correct 9 ms 7584 KB Output is correct
6 Correct 10 ms 7584 KB Output is correct
7 Correct 8 ms 7584 KB Output is correct
8 Correct 8 ms 7596 KB Output is correct
9 Correct 9 ms 7596 KB Output is correct
10 Correct 8 ms 7596 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 11412 KB Output is correct
2 Correct 134 ms 11412 KB Output is correct
3 Correct 508 ms 30220 KB Output is correct
4 Correct 239 ms 30220 KB Output is correct
5 Correct 221 ms 30220 KB Output is correct
6 Incorrect 415 ms 30220 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7380 KB Output is correct
2 Correct 10 ms 7392 KB Output is correct
3 Correct 9 ms 7584 KB Output is correct
4 Correct 7 ms 7584 KB Output is correct
5 Correct 9 ms 7584 KB Output is correct
6 Correct 10 ms 7584 KB Output is correct
7 Correct 8 ms 7584 KB Output is correct
8 Correct 8 ms 7596 KB Output is correct
9 Correct 9 ms 7596 KB Output is correct
10 Correct 8 ms 7596 KB Output is correct
11 Correct 109 ms 11412 KB Output is correct
12 Correct 134 ms 11412 KB Output is correct
13 Correct 508 ms 30220 KB Output is correct
14 Correct 239 ms 30220 KB Output is correct
15 Correct 221 ms 30220 KB Output is correct
16 Incorrect 415 ms 30220 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 30220 KB Output isn't correct
2 Halted 0 ms 0 KB -