oj.uz

Submission #739952

# Submission time Handle Problem Language Result Execution time Memory
739952 2023-05-11T18:22:38 Z rominanafu Tropical Garden (IOI11_garden) C++11
49 / 100
 345 ms 11076 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, 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];
                restar = dist[x];
                x = p_fin[x];
                restar += dist[x];
                x = p_fin[x];
                if (caso >= restar) {
                    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 4692 KB Output is correct
2 Correct 9 ms 4692 KB Output is correct
3 Correct 10 ms 4692 KB Output is correct
4 Correct 2 ms 4692 KB Output is correct
5 Correct 3 ms 4692 KB Output is correct
6 Correct 14 ms 4756 KB Output is correct
7 Correct 2 ms 4692 KB Output is correct
8 Correct 12 ms 4692 KB Output is correct
9 Correct 13 ms 4692 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4692 KB Output is correct
2 Correct 9 ms 4692 KB Output is correct
3 Correct 10 ms 4692 KB Output is correct
4 Correct 2 ms 4692 KB Output is correct
5 Correct 3 ms 4692 KB Output is correct
6 Correct 14 ms 4756 KB Output is correct
7 Correct 2 ms 4692 KB Output is correct
8 Correct 12 ms 4692 KB Output is correct
9 Correct 13 ms 4692 KB Output is correct
10 Correct 3 ms 4692 KB Output is correct
11 Correct 130 ms 5216 KB Output is correct
12 Runtime error 345 ms 11076 KB Execution killed with signal 8
13 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4692 KB Output is correct
2 Correct 9 ms 4692 KB Output is correct
3 Correct 10 ms 4692 KB Output is correct
4 Correct 2 ms 4692 KB Output is correct
5 Correct 3 ms 4692 KB Output is correct
6 Correct 14 ms 4756 KB Output is correct
7 Correct 2 ms 4692 KB Output is correct
8 Correct 12 ms 4692 KB Output is correct
9 Correct 13 ms 4692 KB Output is correct
10 Correct 3 ms 4692 KB Output is correct
11 Correct 130 ms 5216 KB Output is correct
12 Runtime error 345 ms 11076 KB Execution killed with signal 8
13 Halted 0 ms 0 KB -