oj.uz

Submission #399879

# Submission time Handle Problem Language Result Execution time Memory
399879 2021-05-06T19:38:51 Z AugustinasJucas Tropical Garden (IOI11_garden) C++14
100 / 100
 4681 ms 58516 KB 
#pragma GCC optimize("O3")
#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});
   // cout << "dst " << real << ", pb " << v << ", dst = " << h << endl;
  //  }
    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]){
        if(k > n) return ;
        dfs2(v, -1, k);
    }else{
       // cout << "darau nuo " << v << endl;
        int dist = 0;
        while(true){
           // cout << "v = " << v << ", nuo jo iki " << P << " dst = " << dist << endl;
            for(auto x : dst[v]){
                if(x.first & 1) continue;
                if(x.second + dist > k) continue;
                //cout << "bandau " << x.first/2 << endl;
                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.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;
        }
        //cout << "visi: "; for(auto x : visi) cout << x << " ";
        for(auto x : visi) used[x] = 0;
        visi.clear();
        answer(cnt);
    }
    // visada pradesiu nuo 2 * v;
}

Compilation message

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

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 21708 KB Output is correct
2 Correct 14 ms 21644 KB Output is correct
3 Correct 13 ms 21708 KB Output is correct
4 Correct 13 ms 21456 KB Output is correct
5 Correct 13 ms 21424 KB Output is correct
6 Correct 14 ms 21716 KB Output is correct
7 Correct 13 ms 21452 KB Output is correct
8 Correct 14 ms 21572 KB Output is correct
9 Correct 15 ms 21836 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 21708 KB Output is correct
2 Correct 14 ms 21644 KB Output is correct
3 Correct 13 ms 21708 KB Output is correct
4 Correct 13 ms 21456 KB Output is correct
5 Correct 13 ms 21424 KB Output is correct
6 Correct 14 ms 21716 KB Output is correct
7 Correct 13 ms 21452 KB Output is correct
8 Correct 14 ms 21572 KB Output is correct
9 Correct 15 ms 21836 KB Output is correct
10 Correct 13 ms 21404 KB Output is correct
11 Correct 28 ms 25008 KB Output is correct
12 Correct 49 ms 26648 KB Output is correct
13 Correct 76 ms 44592 KB Output is correct
14 Correct 169 ms 36536 KB Output is correct
15 Correct 161 ms 36688 KB Output is correct
16 Correct 126 ms 33512 KB Output is correct
17 Correct 112 ms 31888 KB Output is correct
18 Correct 49 ms 26600 KB Output is correct
19 Correct 152 ms 36568 KB Output is correct
20 Correct 180 ms 36696 KB Output is correct
21 Correct 125 ms 33376 KB Output is correct
22 Correct 118 ms 31912 KB Output is correct
23 Correct 165 ms 39216 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 21708 KB Output is correct
2 Correct 14 ms 21644 KB Output is correct
3 Correct 13 ms 21708 KB Output is correct
4 Correct 13 ms 21456 KB Output is correct
5 Correct 13 ms 21424 KB Output is correct
6 Correct 14 ms 21716 KB Output is correct
7 Correct 13 ms 21452 KB Output is correct
8 Correct 14 ms 21572 KB Output is correct
9 Correct 15 ms 21836 KB Output is correct
10 Correct 13 ms 21404 KB Output is correct
11 Correct 28 ms 25008 KB Output is correct
12 Correct 49 ms 26648 KB Output is correct
13 Correct 76 ms 44592 KB Output is correct
14 Correct 169 ms 36536 KB Output is correct
15 Correct 161 ms 36688 KB Output is correct
16 Correct 126 ms 33512 KB Output is correct
17 Correct 112 ms 31888 KB Output is correct
18 Correct 49 ms 26600 KB Output is correct
19 Correct 152 ms 36568 KB Output is correct
20 Correct 180 ms 36696 KB Output is correct
21 Correct 125 ms 33376 KB Output is correct
22 Correct 118 ms 31912 KB Output is correct
23 Correct 165 ms 39216 KB Output is correct
24 Correct 14 ms 21516 KB Output is correct
25 Correct 64 ms 25100 KB Output is correct
26 Correct 64 ms 26668 KB Output is correct
27 Correct 3731 ms 44744 KB Output is correct
28 Correct 705 ms 36596 KB Output is correct
29 Correct 3244 ms 36928 KB Output is correct
30 Correct 2113 ms 33768 KB Output is correct
31 Correct 2023 ms 31932 KB Output is correct
32 Correct 49 ms 26304 KB Output is correct
33 Correct 716 ms 36668 KB Output is correct
34 Correct 3251 ms 36800 KB Output is correct
35 Correct 2184 ms 33228 KB Output is correct
36 Correct 2021 ms 31908 KB Output is correct
37 Correct 413 ms 41156 KB Output is correct
38 Correct 4681 ms 58516 KB Output is correct