oj.uz

Submission #203151

# Submission time Handle Problem Language Result Execution time Memory
203151 2020-02-19T14:54:32 Z alexandra_udristoiu Tropical Garden (IOI11_garden) C++14
49 / 100
 50 ms 25976 KB 
#include<fstream>
#include<vector>
#include<cstring>
#include "garden.h"
#include "gardenlib.h"
#define DIM 150005
using namespace std;
static int viz[DIM], dist[DIM], t[DIM], cic[DIM], nrcic[DIM], pos[DIM];
static pair<int, int> p[DIM][2];
static vector<int> v[DIM];
static void dfs(int nod){
    viz[nod] = 1;
    for(int i = 0; i < v[nod].size(); i++){
        int vecin = v[nod][i];
        if(viz[vecin] == 0){
            dist[vecin] = 1 + dist[nod];
            dfs(vecin);
        }
    }
}
static void calcp(int i, int x, int y){
    if(p[x][0].first == 0){
        p[x][0] = make_pair(i, y);
    }
    else{
        if(p[x][1].first == 0){
            p[x][1] = make_pair(i, y);
        }
    }
}
static void calct(int x, pair<int, int> curr){
    if(p[ curr.second ][0].first == curr.first && p[ curr.second ][1].first != 0){
        t[x] = 2 * curr.second;
    }
    else{
        t[x] = 2 * curr.second - 1;
    }
}
void count_routes(int n, int m, int d, int w[][2], int q, int g[]){
    int i, x, k, j, sol;
    d++;
    for(i = 0; i < m; i++){
        w[i][0]++;
        w[i][1]++;
        calcp(i + 1, w[i][0], w[i][1]);
        calcp(i + 1, w[i][1], w[i][0]);
    }
    for(i = 1; i <= n; i++){
        calct(2 * i - 1, p[i][0]);
        if(p[i][1].first != 0){
            calct(2 * i, p[i][1]);
        }
        else{
            t[2 * i] = 2 * i;
        }
    }
    k = 0;
    for(i = 1; i <= 2 * n; i++){
        v[ t[i] ].push_back(i);
        x = i;
        while(viz[x] == 0){
            viz[x] = 1;
            pos[x] = i;
            x = t[x];
        }
        if(pos[x] == i){
            k++;
            while(viz[x] != 2){
                viz[x] = 2;
                cic[x] = k;
                nrcic[k]++;
                x = t[x];
            }
        }
    }
    for(i = 0; i < q; i++){
        sol = 0;
        for(x = 2 * d - 1; x <= 2 * d; x++){
            memset(viz, 0, sizeof(viz) );
            dist[x] = 0;
            dfs(x);
            for(j = 1; j <= 2 * n; j += 2){
                if(cic[x] != 0){
                    if(viz[j] == 1 && dist[j] <= g[i] && (dist[j] - g[i]) % nrcic[ cic[x] ] == 0){
                        sol++;
                    }
                }
                else{
                    if(viz[j] == 1 && dist[j] == g[i]){
                        sol++;
                    }
                }
            }
        }
        answer(sol);
    }
}

Compilation message

garden.cpp: In function 'void dfs(int)':
garden.cpp:13:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < v[nod].size(); i++){
                    ~~^~~~~~~~~~~~~~~

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 4600 KB Output is correct
2 Correct 8 ms 4472 KB Output is correct
3 Correct 8 ms 4600 KB Output is correct
4 Correct 7 ms 4472 KB Output is correct
5 Correct 5 ms 4472 KB Output is correct
6 Correct 8 ms 4604 KB Output is correct
7 Correct 7 ms 4472 KB Output is correct
8 Correct 8 ms 4600 KB Output is correct
9 Correct 9 ms 4600 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 4600 KB Output is correct
2 Correct 8 ms 4472 KB Output is correct
3 Correct 8 ms 4600 KB Output is correct
4 Correct 7 ms 4472 KB Output is correct
5 Correct 5 ms 4472 KB Output is correct
6 Correct 8 ms 4604 KB Output is correct
7 Correct 7 ms 4472 KB Output is correct
8 Correct 8 ms 4600 KB Output is correct
9 Correct 9 ms 4600 KB Output is correct
10 Correct 8 ms 4472 KB Output is correct
11 Correct 17 ms 7084 KB Output is correct
12 Correct 32 ms 8824 KB Output is correct
13 Runtime error 50 ms 25976 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 4600 KB Output is correct
2 Correct 8 ms 4472 KB Output is correct
3 Correct 8 ms 4600 KB Output is correct
4 Correct 7 ms 4472 KB Output is correct
5 Correct 5 ms 4472 KB Output is correct
6 Correct 8 ms 4604 KB Output is correct
7 Correct 7 ms 4472 KB Output is correct
8 Correct 8 ms 4600 KB Output is correct
9 Correct 9 ms 4600 KB Output is correct
10 Correct 8 ms 4472 KB Output is correct
11 Correct 17 ms 7084 KB Output is correct
12 Correct 32 ms 8824 KB Output is correct
13 Runtime error 50 ms 25976 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Halted 0 ms 0 KB -