Submission #739950

# Submission time Handle Problem Language Result Execution time Memory
739950 2023-05-11T18:18:09 Z rominanafu Tropical Garden (IOI11_garden) C++11
Compilation error
0 ms 0 KB
#include <bits/stdc++.h>
#define pii pair<int,int>

using namespace std;
typedef long long ll;

int m;
pii s[150005];
bool vis[300005];
short p_fin[300005];
ll dist[300005];
int sig[300005];
int queries, caso, resp;

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];
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    memset(s, -1, sizeof(s));
    memset(dist, -1, sizeof(dist));
    memset(p_fin, -1, sizeof(p_fin));
    int n, fin;
    cin >> n >> m; /// trail 0 > trail 1 > trail 2... (in beauty)
    cin >> fin;
    int a, b;
    while (m--) {
        cin >> a >> b;
        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;
        }
    }
    /// armar grafo:
    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]] == 0) {
        dist[fin] = INT_MAX;
    } else {
        dist[fin] = dist[sig[fin]] + 1;
        p_fin[fin] = p_fin[sig[fin]];
    }
    if (p_fin[sig[fin+n]] == 0) {
        dist[fin+n] = INT_MAX;
    } else {
        dist[fin+n] = dist[sig[fin+n]] + 1;
        p_fin[fin+n] = p_fin[sig[fin+n]];
    }
    int x, c, restar;
    cin >> queries;
    while (queries--) {
        cin >> c;
        resp = 0;
        for(int i=0; i<n; i++) {
            if (p_fin[i] == -1) /// nunca llegó a P
                continue;
            caso = c;
            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++;
                }
            }
        }
        cout << resp << ' ';
    }
    return 0;
}
/**
7 8 5
4 5
5 6
0 1
1 2
2 3
3 6
3 4
4 6
11
1 2 3 4 5 6 7 8 9 10 11
**/

Compilation message

garden.cpp: In function 'int main()':
garden.cpp:30: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]
   30 |     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:1:
/usr/include/c++/10/bits/stl_pair.h:211:12: note: 'struct std::pair<int, int>' declared here
  211 |     struct pair
      |            ^~~~
/usr/bin/ld: /tmp/cc8BarMC.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccIhuhnC.o:garden.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/cc8BarMC.o: in function `main':
grader.cpp:(.text.startup+0x3f): undefined reference to `count_routes(int, int, int, int (*) [2], int, int*)'
collect2: error: ld returned 1 exit status