Submission #501184

#	Time	Username	Problem	Language	Result	Execution time	Memory
501184		doowey	Tropical Garden (IOI11_garden)	C++14	100 / 100	2616 ms	35320 KiB

garden

#include <bits/stdc++.h>
#include "garden.h"
#include "gardenlib.h"

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define fi first
#define se second
#define mp make_pair

const int N = 151515;
const int M = N * 2;

vector<int> T[N];

int id[M];
int ban[M];
int idx = 0;

int n, m, target;

int f[M]; // functional graph

int ret[N][2];

vector<int> qr;
vector<int> res;
int vis[M];
vector<int> TE[M];

vector<int> ord;
bool cyc[M];

vector<int> lis;

void dfs(int u, int par, int ii){
    lis.push_back(u);
    if(ban[u] == false){
        int Z;
        int reach;
        for(int v = 0 ; v < qr.size(); v ++ ){
            Z = qr[v];
            if((int)lis.size() - 1 - Z >= 0){
                reach = lis[lis.size() - 1 - Z];
            }
            else{
                Z -= (int)lis.size() - 1;
                reach = ord[(ii + Z) % ord.size()];
            }
            if(id[reach] == target){
                res[v] ++ ;
            }
        }
    }
    for(auto x : TE[u]){
        if(cyc[x] || par == x) continue;
        dfs(x, u, ii);
    }
    lis.pop_back();
}

void count_routes(int _N, int _M, int _P, int R[][2], int Q, int G[]){
    n = _N;
    m = _M;
    target = _P;
    for(int i = 0 ; i < Q; i ++ ){
        qr.push_back(G[i]);
    }
    res.resize(Q);
    for(int i = 0 ; i < m ; i ++ ){
        T[R[i][0]].push_back(R[i][1]);
        T[R[i][1]].push_back(R[i][0]);
    }
    for(int i = 0; i < n; i ++ ){
        id[idx] = i;
        ban[idx] = 0;
        ret[i][0] = idx;
        idx ++ ;
        id[idx] = i;
        ban[idx] = 1;
        ret[i][1] = idx;
        idx ++ ;
    }
    int nex;
    int ban_nex;
    int node;
    int rq;
    for(int i = 0 ; i < idx; i ++ ){
        node = id[i];
        if(ban[i] == 0){
            nex = T[node][0];
            ban_nex = (T[nex][0] == node);
            f[i] = ret[nex][ban_nex];
        }
        else{

            if(T[node].size() == 1) nex = T[node][0];
            else nex = T[node][1];
            ban_nex = (T[nex][0] == node);
            f[i] = ret[nex][ban_nex];
        }
        TE[f[i]].push_back(i);
        vis[i] = -1;
    }
    int ff;
    int ni;
    for(int i = 0 ; i < idx; i ++ ){
        ff = i;
        while(vis[ff] == -1){
            vis[ff] = i;
            ff = f[ff];
        }
        if(vis[ff] == i){
            ni = ff;
            rq = 0;
            ord.clear();
            do{
                ord.push_back(ni);
                cyc[ni]=true;
                ni = f[ni];
            }while(ni != ff);
            for(int j = 0 ; j < ord.size(); j ++ ){
                dfs(ord[j], -1, j);
            }
        }
    }
    for(int i = 0 ; i < Q; i ++ ){
        answer(res[i]);
    }
}

Compilation message (stderr)

garden.cpp: In function 'void dfs(int, int, int)':
garden.cpp:44:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |         for(int v = 0 ; v < qr.size(); v ++ ){
      |                         ~~^~~~~~~~~~~
garden.cpp: In function 'void count_routes(int, int, int, int (*)[2], int, int*)':
garden.cpp:125:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  125 |             for(int j = 0 ; j < ord.size(); j ++ ){
      |                             ~~^~~~~~~~~~~~
garden.cpp:90:9: warning: variable 'rq' set but not used [-Wunused-but-set-variable]
   90 |     int rq;
      |         ^~

• Subtask 1: 49 / 49
• Subtask 2: 20 / 20
• Subtask 3: 31 / 31