oj.uz

Submission #739959

# Submission time Handle Problem Language Result Execution time Memory
739959 2023-05-11T18:35:42 Z rominanafu Tropical Garden (IOI11_garden) C++11
100 / 100
 3790 ms 13236 KB 
#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
#define pii pair<int,int>

using namespace std;
typedef long long ll;

pii s[150005];
bool vis[300005];
int p_fin[300005];
ll dist[300005];
int sig[300005];

int calc_dist_fin (int act, int &fin) {
    if (vis[act])
        return INT_MAX;
    if (dist[act] != -1)
        return dist[act];
    vis[act] = true;
    dist[act] = calc_dist_fin(sig[act], fin) + 1;
    p_fin[act] = p_fin[sig[act]];
    return dist[act];
}

void count_routes(int n, int m, int fin, int R[][2], int queries, int G[])
{
    memset(s, -1, sizeof(s));
    memset(dist, -1, sizeof(dist));
    memset(p_fin, -1, sizeof(p_fin));
    int a, b;
    for(int i=0; i<m; i++) {
        a = R[i][0];
        b = R[i][1];
        if (s[a].first == -1) {
            s[a].first = b;
        } else if (s[a].second == -1) {
            s[a].second = b;
        }
        if (s[b].first == -1) {
            s[b].first = a;
        } else if (s[b].second == -1) {
            s[b].second = a;
        }
    }
    for(int i=0; i<n; i++) {
        if (s[i].second == -1)
            s[i].second = s[i].first;
        sig[i] = s[i].first;
        if (s[s[i].first].first == i) {
            sig[i] += n;
        }
        sig[i+n] = s[i].second;
        if (s[s[i].second].first == i) {
            sig[i+n] += n;
        }
    }
    dist[fin] = 0;
    dist[fin+n] = 0;
    p_fin[fin] = fin;
    p_fin[fin+n] = fin+n;
    for(int i=0; i<n*2; i++) {
        if (dist[i] == -1) {
            memset(vis, false, sizeof(vis));
            dist[i] = calc_dist_fin(i, fin);
        }
    }
    if (p_fin[sig[fin]] == -1) {
        dist[fin] = INT_MAX;
        p_fin[fin] = -1;
    } else {
        dist[fin] = dist[sig[fin]] + 1;
        p_fin[fin] = p_fin[sig[fin]];
    }
    if (p_fin[sig[fin+n]] == -1) {
        dist[fin+n] = INT_MAX;
        p_fin[fin+n] = -1;
    } else {
        dist[fin+n] = dist[sig[fin+n]] + 1;
        p_fin[fin+n] = p_fin[sig[fin+n]];
    }
    int x, resp, caso, restar;
    for(int k=0; k<queries; k++) {
        resp = 0;
        for(int i=0; i<n; i++) {
            if (p_fin[i] == -1) /// nunca llegó a P
                continue;
            caso = G[k];
            if (dist[i] <= caso) {
                x = i;
                caso -= dist[x];
                x = p_fin[x];
                if (p_fin[x] != p_fin[p_fin[x]]) {
                    restar = dist[x];
                    x = p_fin[x];
                    restar += dist[x];
                    x = p_fin[x];
                } else {
                    if (caso > 0) {
                        caso -= dist[x];
                        x = p_fin[x];
                    }
                    restar = dist[x];
                    x = p_fin[x];
                }
                if (caso > 0) caso -= (caso/restar) * restar;
                while (caso > 0) {
                    caso -= dist[x];
                    x = p_fin[x];
                }
                if (caso == 0) {
                    resp++;
                }
            }
        }
        answer(resp);
    }
}

Compilation message

garden.cpp: In function 'void count_routes(int, int, int, int (*)[2], int, int*)':
garden.cpp:28:28: warning: 'void* memset(void*, int, size_t)' writing to an object of type 'struct std::pair<int, int>' with no trivial copy-assignment [-Wclass-memaccess]
   28 |     memset(s, -1, sizeof(s));
      |                            ^
In file included from /usr/include/c++/10/bits/stl_algobase.h:64,
                 from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from garden.cpp:3:
/usr/include/c++/10/bits/stl_pair.h:211:12: note: 'struct std::pair<int, int>' declared here
  211 |     struct pair
      |            ^~~~

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5332 KB Output is correct
2 Correct 9 ms 5332 KB Output is correct
3 Correct 9 ms 5324 KB Output is correct
4 Correct 3 ms 5204 KB Output is correct
5 Correct 2 ms 5204 KB Output is correct
6 Correct 9 ms 5340 KB Output is correct
7 Correct 2 ms 5204 KB Output is correct
8 Correct 12 ms 5328 KB Output is correct
9 Correct 13 ms 5332 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5332 KB Output is correct
2 Correct 9 ms 5332 KB Output is correct
3 Correct 9 ms 5324 KB Output is correct
4 Correct 3 ms 5204 KB Output is correct
5 Correct 2 ms 5204 KB Output is correct
6 Correct 9 ms 5340 KB Output is correct
7 Correct 2 ms 5204 KB Output is correct
8 Correct 12 ms 5328 KB Output is correct
9 Correct 13 ms 5332 KB Output is correct
10 Correct 3 ms 5204 KB Output is correct
11 Correct 123 ms 5716 KB Output is correct
12 Correct 336 ms 6152 KB Output is correct
13 Correct 604 ms 9192 KB Output is correct
14 Correct 1314 ms 9120 KB Output is correct
15 Correct 1382 ms 9256 KB Output is correct
16 Correct 891 ms 8708 KB Output is correct
17 Correct 887 ms 8492 KB Output is correct
18 Correct 346 ms 6580 KB Output is correct
19 Correct 1305 ms 9184 KB Output is correct
20 Correct 1325 ms 9260 KB Output is correct
21 Correct 857 ms 8644 KB Output is correct
22 Correct 723 ms 8496 KB Output is correct
23 Correct 1395 ms 9556 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5332 KB Output is correct
2 Correct 9 ms 5332 KB Output is correct
3 Correct 9 ms 5324 KB Output is correct
4 Correct 3 ms 5204 KB Output is correct
5 Correct 2 ms 5204 KB Output is correct
6 Correct 9 ms 5340 KB Output is correct
7 Correct 2 ms 5204 KB Output is correct
8 Correct 12 ms 5328 KB Output is correct
9 Correct 13 ms 5332 KB Output is correct
10 Correct 3 ms 5204 KB Output is correct
11 Correct 123 ms 5716 KB Output is correct
12 Correct 336 ms 6152 KB Output is correct
13 Correct 604 ms 9192 KB Output is correct
14 Correct 1314 ms 9120 KB Output is correct
15 Correct 1382 ms 9256 KB Output is correct
16 Correct 891 ms 8708 KB Output is correct
17 Correct 887 ms 8492 KB Output is correct
18 Correct 346 ms 6580 KB Output is correct
19 Correct 1305 ms 9184 KB Output is correct
20 Correct 1325 ms 9260 KB Output is correct
21 Correct 857 ms 8644 KB Output is correct
22 Correct 723 ms 8496 KB Output is correct
23 Correct 1395 ms 9556 KB Output is correct
24 Correct 5 ms 5332 KB Output is correct
25 Correct 186 ms 6028 KB Output is correct
26 Correct 407 ms 6872 KB Output is correct
27 Correct 1655 ms 10300 KB Output is correct
28 Correct 2309 ms 9296 KB Output is correct
29 Correct 3790 ms 9296 KB Output is correct
30 Correct 2282 ms 8744 KB Output is correct
31 Correct 2221 ms 8528 KB Output is correct
32 Correct 480 ms 6620 KB Output is correct
33 Correct 1998 ms 9212 KB Output is correct
34 Correct 3748 ms 9292 KB Output is correct
35 Correct 2263 ms 8800 KB Output is correct
36 Correct 2021 ms 8564 KB Output is correct
37 Correct 1857 ms 9716 KB Output is correct
38 Correct 1960 ms 13236 KB Output is correct