Submission #399847

#	Time	Username	Problem	Language	Result	Execution time	Memory
399847		AugustinasJucas	Tropical Garden (IOI11_garden)	C++14	0 / 100	12 ms	21708 KiB

garden

#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
using namespace std;
const int dydis = 2 * 150000 + 10;
vector<pair<int, int> > gr[dydis];
int n, m;
int nxt[dydis];
vector<int> rev[dydis];
bool vis[dydis];
bool on[dydis];
bool inCyc[dydis] = {};
int revCyc[dydis];
vector<int> cur; vector<int> cyc;
vector<pair<int, int> > dst[dydis];
vector<int> visi;
int sz[dydis] = {0};
bool used[dydis];
void dfs(int v){
    //cout << "v = " << v << endl;
    if(cyc.size() != 0) return;
    if(vis[v]){
        if(!on[v]) return ;

        while(true){
            cyc.push_back(cur.back());
            int lst = cur.back();
            cur.pop_back();
            if(lst == v) break;
        }
        return ;
    }
    vis[v] = 1;
    on[v] = 1;
    cur.push_back(v);
    dfs(nxt[v]);
    on[v] = 0;
    if(cur.size())cur.pop_back();
}
void dfs1(int v, int came, int real, int h = 0){
  //  if(v != real){
        dst[real].push_back({v, h});
  //  }
    for(auto x : rev[v]){
        if(x == came || inCyc[x]) continue;
        dfs1(x, v, real, h+1);
    }
}
void dfs2(int v, int came, int left){
    int ret = 0;
    if(left == 0) {
        if(!(v & 1)) visi.push_back(v/2);
        return;
    }
    for(auto x : rev[v]){
        if(x == came) continue;
        dfs2(x, v, left-1);
    }
}
void darom(int v, int k){
    int P = v;
    //cout << "kiek nuo " << v << " " << k << endl;
    if(!inCyc[v]){
        dfs2(v, -1, k);

    }else{
        int dist = 0;
        while(true){
            for(auto x : dst[v]){
                if(x.first & 1) continue;
                if(x.second + dist < k) continue;
                if((k-x.second) % sz[P] == dist){
                    visi.push_back(x.first/2);
                }
                // jo atstumas yra
            }
            dist++;
            v = revCyc[v];
            if(v == P) break;
        }

    }
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[]) {
    //cout << "start" << endl;
    n = N; m = M;
    for(int i = 0; i < m; i++){
        gr[R[i][0]].push_back({R[i][1], i});
        gr[R[i][1]].push_back({R[i][0], i});
    }
    //for(int i = 0; i < n; i++) reverse(gr[i].begin(), gr[i].end());
    for(int i = 0; i < 2 * n; i++){
        int v = i / 2;
        int kt = -1; int kn = 0;
        if(i & 1) { // atejau is didziausio savo
            if(gr[v].size() == 1){
                kt = gr[v][0].first;
                kn = gr[v][0].second;
            }else{
                kt = gr[v][1].first;
                kn = gr[v][1].second;
            }
        }else{
            kt = gr[v][0].first;
            kn = gr[v][0].second;
        }
        if(gr[kt][0].second == kn){
            nxt[i] = 2 * kt + 1;
            rev[2*kt+1].push_back(i);
        }else{
            nxt[i] = 2 * kt;
            rev[2*kt].push_back(i);
        }
        //cout << "nxt[" << i << "] = " << nxt[i] << endl;
    }

    for(int i = 0; i < 2*n; i++){
        if(vis[i]) continue;
        cur.clear(); cyc.clear();
        dfs(i);
        if(cyc.size() == 0) continue;
       // cout << "cyc = "; for(auto x : cyc) cout << x << " "; cout << "\n";
        for(auto x : cyc) inCyc[x] = 1;
        for(auto x : cyc) dfs1(x, x, x);
        for(int i = 0; i < cyc.size(); i++){
            revCyc[cyc[(i+1)%cyc.size()]] = cyc[i];
            sz[cyc[i]] = cyc.size();
        }
    }
    for(int i = 0; i < Q; i++){
        int k = G[i];
        darom(P*2, k);
        darom(P*2+1, k);
        int cnt = 0;
        for(auto x : visi){
            if(!used[x]) cnt++;
            used[x] = 1;
        }
        for(auto x : visi) used[x] = 0;
        visi.clear();
        answer(cnt);
    }
    // visada pradesiu nuo 2 * v;
}

Compilation message (stderr)

garden.cpp: In function 'void dfs2(int, int, int)':
garden.cpp:51:9: warning: unused variable 'ret' [-Wunused-variable]
   51 |     int ret = 0;
      |         ^~~
garden.cpp: In function 'void count_routes(int, int, int, int (*)[2], int, int*)':
garden.cpp:126:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  126 |         for(int i = 0; i < cyc.size(); i++){
      |                        ~~^~~~~~~~~~~~

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