Submission #360923

#	Time	Username	Problem	Language	Result	Execution time	Memory
360923		sean617	Tropical Garden (IOI11_garden)	C++98	0 / 100	13 ms	19948 KiB

garden

#include "garden.h"
#include "gardenlib.h"
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#define L 150005
using namespace std;

int ty;
int n, m, st, cnt1, cnt, cnt2, fi[L], se[L], b[L][2][2], la[L][2], l[L][2];
bool v[L][2], v2[L][2], v3[L][2], ans[L];
vector<int> a[L], c[L][2][2];
void f(int p, int q) {
    int t;
//    if (v[p][q]) return;
//    v[p][q] = 1;
    if (q == 0) {
        t = fi[p];
    } else {
        t = se[p];
    }
    b[p][q][0] = t;
    b[p][q][1] = (fi[t] == p);
//    f(t, (fi[t] == p));
}

void g(int p, int q) {
    int i, cnt, t1, t2, j1, j2;
    if (v2[p][q]) {
        j1 = p;
        j2 = q;
        cnt = 0;
        while (1) {
            cnt++;
            t1 = c[j1][j2][0][la[j1][j2]];
            t2 = c[j1][j2][1][la[j1][j2]];
            j1 = t1;
            j2 = t2;
            if (j1 == p && j2 == q) break;
        }
        if (ty == 0) cnt1 = cnt;
        else cnt2 = cnt;
        return;
    }
    v2[p][q] = 1;
    for (i =0; i < c[p][q][0].size(); i++) {
        la[p][q] = i;
        g(c[p][q][0][i], c[p][q][1][i]);
    }
}

void g2(int p, int q, int w) {
    int i;
    if (v3[p][q]) return;
    v3[p][q] = 1;
    if (q == 0) l[p][ty] = w;
    for (i = 0; i < c[p][q][0].size(); i++) {
        g2(c[p][q][0][i], c[p][q][1][i], w + 1);
    }
}

void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
    int i, j, t, t1, t2;
//    freopen ("input.txt", "r", stdin);
    n = N;
    m = M;
    st = P;
    for (i = 0; i < m; i++) {
        t1 = R[i][0];
        t2 = R[i][1];
        a[t1].push_back(t2);
        a[t2].push_back(t1);
    }
    for (i = 0; i < n; i++) {
        fi[i] = a[i][0];
        if (a[i].size() == 1) se[i] = a[i][0];
        else se[i] = a[i][1];
    }
//    for (i = 0; i < n; i++) {
//        printf("%d %d\n", fi[i], se[i]);
//    }

    for (i = 0; i < n; i++) {
        f(i, 0);
        f(i, 1);
    }

    for (i = 0; i < n; i++) {
        for (j = 0; j < 2; j++) {
            c[b[i][j][0]][b[i][j][1]][0].push_back(i);
            c[b[i][j][0]][b[i][j][1]][1].push_back(j);
//            printf("%d %d %d %d\n", i, j, b[i][j][0], b[i][j][1]);
        }
    }
    memset(l, -1, sizeof(l));
    ty = 0;
    cnt = 0;
    g(st, 0);
    g2(st, 0, 0);
    memset(v2, 0, sizeof(v2));
    memset(v3, 0, sizeof(v3));
    ty = 1;
    cnt = 0;
    g(st, 1);
    g2(st, 1, 0);
    int anscnt;
    while (Q--) {
        t = G[i];
        anscnt = 0;
        for (i = 0; i < n; i++) {
            if (t == l[i][0] || l[i][0] != -1 && t > l[i][0] && cnt1 > 0 && (t - l[i][0]) % cnt1 == 0) anscnt++;
            else if (t == l[i][1] || l[i][1] != -1 && t > l[i][1] && cnt2 > 0 && (t - l[i][1]) % cnt2 == 0) anscnt++;
        }
        answer(anscnt);
    }
}

Compilation message (stderr)

garden.cpp: In function 'void g(int, int)':
garden.cpp:47:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |     for (i =0; i < c[p][q][0].size(); i++) {
      |                ~~^~~~~~~~~~~~~~~~~~~
garden.cpp: In function 'void g2(int, int, int)':
garden.cpp:58:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |     for (i = 0; i < c[p][q][0].size(); i++) {
      |                 ~~^~~~~~~~~~~~~~~~~~~
garden.cpp: In function 'void count_routes(int, int, int, int (*)[2], int, int*)':
garden.cpp:113:74: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  113 |             if (t == l[i][0] || l[i][0] != -1 && t > l[i][0] && cnt1 > 0 && (t - l[i][0]) % cnt1 == 0) anscnt++;
      |                                 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
garden.cpp:114:79: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  114 |             else if (t == l[i][1] || l[i][1] != -1 && t > l[i][1] && cnt2 > 0 && (t - l[i][1]) % cnt2 == 0) anscnt++;
      |                                      ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 49
• Subtask 2: 0 / 20
• Subtask 3: 0 / 31