oj.uz

Submission #739924

# Submission time Handle Problem Language Result Execution time Memory
739924 2023-05-11T15:58:00 Z rominanafu Tropical Garden (IOI11_garden) C++11
49 / 100
 5000 ms 9596 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];
short 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;
    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;
                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 4736 KB Output is correct
2 Correct 8 ms 4752 KB Output is correct
3 Correct 9 ms 4668 KB Output is correct
4 Correct 3 ms 4692 KB Output is correct
5 Correct 3 ms 4692 KB Output is correct
6 Correct 9 ms 4692 KB Output is correct
7 Correct 2 ms 4692 KB Output is correct
8 Correct 12 ms 4756 KB Output is correct
9 Correct 14 ms 4820 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4736 KB Output is correct
2 Correct 8 ms 4752 KB Output is correct
3 Correct 9 ms 4668 KB Output is correct
4 Correct 3 ms 4692 KB Output is correct
5 Correct 3 ms 4692 KB Output is correct
6 Correct 9 ms 4692 KB Output is correct
7 Correct 2 ms 4692 KB Output is correct
8 Correct 12 ms 4756 KB Output is correct
9 Correct 14 ms 4820 KB Output is correct
10 Correct 3 ms 4636 KB Output is correct
11 Correct 135 ms 5372 KB Output is correct
12 Correct 385 ms 6144 KB Output is correct
13 Execution timed out 5067 ms 9596 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4736 KB Output is correct
2 Correct 8 ms 4752 KB Output is correct
3 Correct 9 ms 4668 KB Output is correct
4 Correct 3 ms 4692 KB Output is correct
5 Correct 3 ms 4692 KB Output is correct
6 Correct 9 ms 4692 KB Output is correct
7 Correct 2 ms 4692 KB Output is correct
8 Correct 12 ms 4756 KB Output is correct
9 Correct 14 ms 4820 KB Output is correct
10 Correct 3 ms 4636 KB Output is correct
11 Correct 135 ms 5372 KB Output is correct
12 Correct 385 ms 6144 KB Output is correct
13 Execution timed out 5067 ms 9596 KB Time limit exceeded
14 Halted 0 ms 0 KB -