oj.uz

Submission #739956

# Submission time Handle Problem Language Result Execution time Memory
739956 2023-05-11T18:26:42 Z rominanafu Tropical Garden (IOI11_garden) C++11
49 / 100
 568 ms 10168 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];
                restar = dist[x];
                x = p_fin[x];
                restar = dist[x];
                x = p_fin[x];
                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 5204 KB Output is correct
3 Correct 8 ms 5332 KB Output is correct
4 Correct 2 ms 5204 KB Output is correct
5 Correct 2 ms 5204 KB Output is correct
6 Correct 9 ms 5336 KB Output is correct
7 Correct 3 ms 5204 KB Output is correct
8 Correct 12 ms 5328 KB Output is correct
9 Correct 13 ms 5376 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5332 KB Output is correct
2 Correct 9 ms 5204 KB Output is correct
3 Correct 8 ms 5332 KB Output is correct
4 Correct 2 ms 5204 KB Output is correct
5 Correct 2 ms 5204 KB Output is correct
6 Correct 9 ms 5336 KB Output is correct
7 Correct 3 ms 5204 KB Output is correct
8 Correct 12 ms 5328 KB Output is correct
9 Correct 13 ms 5376 KB Output is correct
10 Correct 3 ms 5204 KB Output is correct
11 Correct 122 ms 5716 KB Output is correct
12 Correct 339 ms 6140 KB Output is correct
13 Incorrect 568 ms 10168 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5332 KB Output is correct
2 Correct 9 ms 5204 KB Output is correct
3 Correct 8 ms 5332 KB Output is correct
4 Correct 2 ms 5204 KB Output is correct
5 Correct 2 ms 5204 KB Output is correct
6 Correct 9 ms 5336 KB Output is correct
7 Correct 3 ms 5204 KB Output is correct
8 Correct 12 ms 5328 KB Output is correct
9 Correct 13 ms 5376 KB Output is correct
10 Correct 3 ms 5204 KB Output is correct
11 Correct 122 ms 5716 KB Output is correct
12 Correct 339 ms 6140 KB Output is correct
13 Incorrect 568 ms 10168 KB Output isn't correct
14 Halted 0 ms 0 KB -