Submission #203152

#	Time	Username	Problem	Language	Result	Execution time	Memory
203152		alexandra_udristoiu	Tropical Garden (IOI11_garden)	C++14	69 / 100	5016 ms	25976 KiB

garden

#include<fstream>
#include<vector>
#include<cstring>
#include "garden.h"
#include "gardenlib.h"
#define DIM 300005
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 (stderr)

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 / 49
• Subtask 2: 20 / 20
• Subtask 3: 0 / 31