oj.uz

Submission #58705

# Submission time Handle Problem Language Result Execution time Memory
58705 2018-07-19T00:33:34 Z onjo0127(#1933) Paths (BOI18_paths) C++11
23 / 100
 3000 ms 36404 KB 
#include <bits/stdc++.h>
using namespace std;

vector<int> adj[300009];
int color[300009], ans;
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);
    }
    for(int i=1; i<=N; i++) go(i, K-1);
    printf("%d", ans - N);
    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 9 ms 7288 KB Output is correct
2 Correct 11 ms 7568 KB Output is correct
3 Correct 10 ms 7568 KB Output is correct
4 Correct 10 ms 7568 KB Output is correct
5 Correct 12 ms 7568 KB Output is correct
6 Correct 11 ms 7568 KB Output is correct
7 Correct 10 ms 7616 KB Output is correct
8 Correct 10 ms 7668 KB Output is correct
9 Correct 12 ms 7728 KB Output is correct
10 Correct 10 ms 7792 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 702 ms 14324 KB Output is correct
2 Correct 2700 ms 16388 KB Output is correct
3 Correct 521 ms 27252 KB Output is correct
4 Correct 274 ms 27252 KB Output is correct
5 Correct 195 ms 28648 KB Output is correct
6 Execution timed out 3063 ms 36404 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7288 KB Output is correct
2 Correct 11 ms 7568 KB Output is correct
3 Correct 10 ms 7568 KB Output is correct
4 Correct 10 ms 7568 KB Output is correct
5 Correct 12 ms 7568 KB Output is correct
6 Correct 11 ms 7568 KB Output is correct
7 Correct 10 ms 7616 KB Output is correct
8 Correct 10 ms 7668 KB Output is correct
9 Correct 12 ms 7728 KB Output is correct
10 Correct 10 ms 7792 KB Output is correct
11 Correct 702 ms 14324 KB Output is correct
12 Correct 2700 ms 16388 KB Output is correct
13 Correct 521 ms 27252 KB Output is correct
14 Correct 274 ms 27252 KB Output is correct
15 Correct 195 ms 28648 KB Output is correct
16 Execution timed out 3063 ms 36404 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 36404 KB Output is correct
2 Execution timed out 3066 ms 36404 KB Time limit exceeded
3 Halted 0 ms 0 KB -