oj.uz

Submission #185209

# Submission time Handle Problem Language Result Execution time Memory
185209 2020-01-11T08:29:11 Z Ruxandra985 Paths (BOI18_paths) C++14
53 / 100
 251 ms 44820 KB 
#include <bits/stdc++.h>

using namespace std;
deque <pair <int,int> > dq;
long long dp[32][100010];
int cul[100010] , f[32][100010];
vector <int> v[100010];
int main()
{
    FILE *fin = stdin;
    FILE *fout = stdout;
    int n , m , k , i , j , nod , vecin , conf , x, y;
    long long sol;
    fscanf (fin,"%d%d%d",&n,&m,&k);
    for (i=1;i<=n;i++){
        fscanf (fin,"%d",&cul[i]);
        cul[i]--;
        dp[(1 << cul[i])][i] = 1;
        f[(1 << cul[i])][i] = 1;
        dq.push_back(make_pair((1 << cul[i]) , i));
    }
    for (i=1;i<=m;i++){
        fscanf (fin,"%d%d",&x,&y);
        v[x].push_back(y);
        v[y].push_back(x);
    }
    while (!dq.empty()){
        conf = dq.front().first;
        nod = dq.front().second;
        dq.pop_front();
        for (i=0;i<v[nod].size();i++){
            vecin = v[nod][i];
            if ((conf & ( 1 << cul[vecin])) == 0){
                dp[(conf | ( 1 << cul[vecin]))][vecin] += dp[conf][nod];
                if (!f[(conf | ( 1 << cul[vecin]))][vecin]){
                    f[(conf | ( 1 << cul[vecin]))][vecin] = 1;
                    dq.push_back(make_pair( (conf | ( 1 << cul[vecin])) , vecin ));
                }
            }
        }
    }
    sol = 0;
    for (i=0;i<32;i++)
        for (j=1;j<=n;j++)
            sol+=dp[i][j];
    fprintf (fout,"%lld",sol - n);
    return 0;
}

Compilation message

paths.cpp: In function 'int main()':
paths.cpp:31:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (i=0;i<v[nod].size();i++){
                  ~^~~~~~~~~~~~~~
paths.cpp:14:12: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     fscanf (fin,"%d%d%d",&n,&m,&k);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
paths.cpp:16:16: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         fscanf (fin,"%d",&cul[i]);
         ~~~~~~~^~~~~~~~~~~~~~~~~~
paths.cpp:23:16: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         fscanf (fin,"%d%d",&x,&y);
         ~~~~~~~^~~~~~~~~~~~~~~~~~

Subtask #1
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2936 KB Output is correct
2 Correct 5 ms 2936 KB Output is correct
3 Correct 4 ms 2808 KB Output is correct
4 Correct 5 ms 2808 KB Output is correct
5 Correct 5 ms 2808 KB Output is correct
6 Correct 5 ms 2808 KB Output is correct
7 Correct 5 ms 2808 KB Output is correct
8 Correct 5 ms 2812 KB Output is correct
9 Correct 4 ms 2680 KB Output is correct
10 Correct 5 ms 2720 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 9580 KB Output is correct
2 Correct 95 ms 8784 KB Output is correct
3 Runtime error 70 ms 27768 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2936 KB Output is correct
2 Correct 5 ms 2936 KB Output is correct
3 Correct 4 ms 2808 KB Output is correct
4 Correct 5 ms 2808 KB Output is correct
5 Correct 5 ms 2808 KB Output is correct
6 Correct 5 ms 2808 KB Output is correct
7 Correct 5 ms 2808 KB Output is correct
8 Correct 5 ms 2812 KB Output is correct
9 Correct 4 ms 2680 KB Output is correct
10 Correct 5 ms 2720 KB Output is correct
11 Correct 126 ms 9580 KB Output is correct
12 Correct 95 ms 8784 KB Output is correct
13 Runtime error 70 ms 27768 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Halted 0 ms 0 KB -

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 55 ms 5020 KB Output is correct
3 Correct 37 ms 4600 KB Output is correct
4 Correct 146 ms 16392 KB Output is correct
5 Correct 145 ms 16240 KB Output is correct
6 Correct 251 ms 44792 KB Output is correct
7 Correct 39 ms 4728 KB Output is correct
8 Correct 148 ms 25848 KB Output is correct
9 Correct 112 ms 21720 KB Output is correct
10 Correct 139 ms 20180 KB Output is correct
11 Correct 130 ms 26124 KB Output is correct
12 Correct 115 ms 19368 KB Output is correct
13 Correct 126 ms 20412 KB Output is correct
14 Correct 190 ms 44816 KB Output is correct
15 Correct 174 ms 44820 KB Output is correct
16 Correct 4 ms 2808 KB Output is correct
17 Correct 13 ms 2908 KB Output is correct
18 Correct 4 ms 2808 KB Output is correct
19 Correct 4 ms 2808 KB Output is correct
20 Correct 4 ms 2680 KB Output is correct
21 Correct 4 ms 2812 KB Output is correct
22 Correct 5 ms 2780 KB Output is correct
23 Correct 4 ms 2912 KB Output is correct
24 Correct 4 ms 2808 KB Output is correct
25 Correct 5 ms 2808 KB Output is correct