oj.uz

Submission #659543

# Submission time Handle Problem Language Result Execution time Memory
659543 2022-11-18T12:50:49 Z Soul234 Tropical Garden (IOI11_garden) C++14
100 / 100
 2363 ms 28436 KB 
#include "garden.h"
#include "gardenlib.h"

#include<bits/stdc++.h>
using namespace std;

void DBG() { cerr << "]\n"; }
template<class H, class... T> void DBG(H h, T... t) {
    cerr << h; if(sizeof...(t)) cerr << ", ";
    DBG(t...);
}
#ifdef LOCAL
#define dbg(...) cerr << "[" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__)
#else
#define dbg(...) 0
#endif // LOCAL

#define FOR(i,a,b) for(int i = (a) ; i<(b) ; i++)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for(int i = (b)-1 ; i>=(a) ; i--)
#define R0F(i,a) ROF(i,0,a)
#define each(e,a) for(auto &e : (a))
#define sz(v) (int)(v).size()
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define pb push_back
#define tcT template<class T
#define nl "\n"
#define fi first
#define se second

using ll = long long;
using vi = vector<int>;
using pi = pair<int,int>;
using str = string;
using db = long double;
tcT> using V = vector<T>;
tcT> using pqg = priority_queue<T,vector<T>,greater<T>>;

void setIO(string NAME = "") {
    cin.tie(0)->sync_with_stdio(0);
    if(sz(NAME)) {
        freopen((NAME + ".inp").c_str(),"r",stdin);
        freopen((NAME + ".out").c_str(),"w",stdout);
    }
}

tcT> bool ckmin(T&a, const T&b) {
    return b < a ? a=b,1 : 0; }
tcT> bool ckmax(T&a, const T&b) {
    return b > a ? a=b,1 : 0; }

const int MOD = 1e9 + 7;
const ll INF = 1e18;

const int MX = 150005;

vi adj[MX<<1];

int fs[MX<<1], sc[MX<<1];

int nxt[MX<<1];

int dist[2][MX<<1];
int cycsz[2], cycDist[2][MX<<1];

bool vis[MX<<1];
int goal;

void dfs(int u, int id) {
    if(~dist[id][u]) return;
    if(~cycDist[id][u]) {
        dist[id][u] = cycDist[id][u];
        return;
    }
    if(u == goal) {
        dist[id][u] = 0;
        return;
    }
    dist[id][u] = MOD;
    if(dist[id][nxt[u]] == -1) dfs(nxt[u], id);
    ckmin(dist[id][u], dist[id][nxt[u]] + 1);
}

void count_routes(int N, int M, int P, int R[][2], int Q, int G[]) {
    memset(fs, -1, sizeof fs);
    memset(sc, -1, sizeof sc);

    R0F(i, M) {
        sc[R[i][0]] = fs[R[i][0]];
        fs[R[i][0]] = R[i][1];
        sc[R[i][1]] = fs[R[i][1]];
        fs[R[i][1]] = R[i][0];
    }

    F0R(i, N<<1) {
        if(i < N) {
            if(fs[fs[i]] == i) {
                nxt[i] = fs[i] + N;
            }
            else {
                nxt[i] = fs[i];
            }
        }
        else {
            if(sc[i-N] == -1) {
                nxt[i] = nxt[i-N];
            }
            else if(fs[sc[i-N]] == i-N) {
                nxt[i] = sc[i-N] + N;
            }
            else nxt[i] = sc[i-N];
        }
    }

    memset(cycDist, -1, sizeof cycDist);
    memset(dist, -1, sizeof dist);

    F0R(id, 2) {
        memset(vis, false, sizeof vis);
        int cur = P + id*N;
        while(cur >= 0 && !vis[cur]) {
            vis[cur] = 1;
            cycDist[id][cur] = cycsz[id]++;
            cur = nxt[cur];
        }

        F0R(i, N<<1) {
            if(~cycDist[id][i]) {
                cycDist[id][i] = (cycsz[id] - cycDist[id][i])%cycsz[id];
            }
        }

        goal = -1;

        if(cur != P + id*N) {
            cycsz[id] = 0;
            memset(cycDist[id], -1, sizeof cycDist[id]);
            goal = P + id*N;
        }

        F0R(i, N) if(dist[id][i] == -1) dfs(i, id);
    }


    F0R(i, Q) {
        int K = G[i];
        bool ok = false;
        int cnt = 0;
        F0R(u, N) {
            bool ok = false;
            F0R(id, 2) {
                ok |= (dist[id][u] == K || (cycsz[id] > 0 && K >= dist[id][u] && (K - dist[id][u])%cycsz[id] == 0));
            }
            cnt += ok;
        }
        answer(cnt);
    }
}

Compilation message

garden.cpp: In function 'void count_routes(int, int, int, int (*)[2], int, int*)':
garden.cpp:148:14: warning: unused variable 'ok' [-Wunused-variable]
  148 |         bool ok = false;
      |              ^~
garden.cpp: In function 'void setIO(std::string)':
garden.cpp:43:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |         freopen((NAME + ".inp").c_str(),"r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
garden.cpp:44:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 |         freopen((NAME + ".out").c_str(),"w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14672 KB Output is correct
2 Correct 7 ms 14676 KB Output is correct
3 Correct 7 ms 14660 KB Output is correct
4 Correct 9 ms 14676 KB Output is correct
5 Correct 7 ms 14676 KB Output is correct
6 Correct 8 ms 14748 KB Output is correct
7 Correct 9 ms 14676 KB Output is correct
8 Correct 7 ms 14676 KB Output is correct
9 Correct 9 ms 14932 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14672 KB Output is correct
2 Correct 7 ms 14676 KB Output is correct
3 Correct 7 ms 14660 KB Output is correct
4 Correct 9 ms 14676 KB Output is correct
5 Correct 7 ms 14676 KB Output is correct
6 Correct 8 ms 14748 KB Output is correct
7 Correct 9 ms 14676 KB Output is correct
8 Correct 7 ms 14676 KB Output is correct
9 Correct 9 ms 14932 KB Output is correct
10 Correct 6 ms 14676 KB Output is correct
11 Correct 12 ms 15572 KB Output is correct
12 Correct 17 ms 16212 KB Output is correct
13 Correct 26 ms 16972 KB Output is correct
14 Correct 37 ms 18528 KB Output is correct
15 Correct 50 ms 18608 KB Output is correct
16 Correct 37 ms 18168 KB Output is correct
17 Correct 33 ms 17824 KB Output is correct
18 Correct 18 ms 15948 KB Output is correct
19 Correct 36 ms 18420 KB Output is correct
20 Correct 39 ms 18756 KB Output is correct
21 Correct 36 ms 18068 KB Output is correct
22 Correct 39 ms 17868 KB Output is correct
23 Correct 47 ms 19072 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14672 KB Output is correct
2 Correct 7 ms 14676 KB Output is correct
3 Correct 7 ms 14660 KB Output is correct
4 Correct 9 ms 14676 KB Output is correct
5 Correct 7 ms 14676 KB Output is correct
6 Correct 8 ms 14748 KB Output is correct
7 Correct 9 ms 14676 KB Output is correct
8 Correct 7 ms 14676 KB Output is correct
9 Correct 9 ms 14932 KB Output is correct
10 Correct 6 ms 14676 KB Output is correct
11 Correct 12 ms 15572 KB Output is correct
12 Correct 17 ms 16212 KB Output is correct
13 Correct 26 ms 16972 KB Output is correct
14 Correct 37 ms 18528 KB Output is correct
15 Correct 50 ms 18608 KB Output is correct
16 Correct 37 ms 18168 KB Output is correct
17 Correct 33 ms 17824 KB Output is correct
18 Correct 18 ms 15948 KB Output is correct
19 Correct 36 ms 18420 KB Output is correct
20 Correct 39 ms 18756 KB Output is correct
21 Correct 36 ms 18068 KB Output is correct
22 Correct 39 ms 17868 KB Output is correct
23 Correct 47 ms 19072 KB Output is correct
24 Correct 8 ms 14672 KB Output is correct
25 Correct 101 ms 15616 KB Output is correct
26 Correct 138 ms 16424 KB Output is correct
27 Correct 2166 ms 17156 KB Output is correct
28 Correct 871 ms 18564 KB Output is correct
29 Correct 2363 ms 18700 KB Output is correct
30 Correct 1349 ms 18244 KB Output is correct
31 Correct 1311 ms 18056 KB Output is correct
32 Correct 118 ms 16012 KB Output is correct
33 Correct 879 ms 18592 KB Output is correct
34 Correct 2307 ms 18748 KB Output is correct
35 Correct 1447 ms 18096 KB Output is correct
36 Correct 1346 ms 17992 KB Output is correct
37 Correct 718 ms 19152 KB Output is correct
38 Correct 1891 ms 28436 KB Output is correct