제출 #347869

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
347869		idk321	열대 식물원 (Tropical Garden) (IOI11_garden)	C++11	0 / 100	175 ms	262148 KiB

garden

#include "garden.h"
#include "gardenlib.h"

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int N = 150001;
vector<array<int, 2>> adj[N];
int dist[N][2][2];
int onCycle[N][2];
int p;

void dfs(int node, int type, int c)
{

    //cout << "oj " << node << " " << type << " " <<dist[node][type][c] << endl;
    for (int i = 0; i < adj[node].size(); i++)
    {
        if (adj[node].size() > 1 && i == type) continue;
        if (type == 1 && i > 0) continue;
        auto adjacent = adj[node][i];
        //cout << "eh " << node << " " << type << " " << dist[node][type][c] << " " << adjacent[0] << endl;
        int next = -1;
        if (adj[adjacent[0]].size() == 1 || adj[adjacent[0]][0][1] == adjacent[1])
        {
            next = 0;
        } else if (adj[adjacent[0]][1][1] == adjacent[1])
        {
            next = 1;
        }
        if (next != -1)
        {
            if (adjacent[0] == p && next == c)
            {
                onCycle[p][c] = dist[node][type][c] + 1;
                continue;
            }
            dist[adjacent[0]][next][c] = dist[node][type][c] + 1;
            dfs(adjacent[0], next, c);
        }
    }
}

void count_routes(int n, int m, int pa, int R[][2], int Q, int G[])
{

    p = pa;
  for (int i = 0; i < m; i++)
  {
    adj[R[i][0]].push_back({R[i][1], i + 1});
    adj[R[i][1]].push_back({R[i][0], i + 1});
  }

  for (int i = 0; i < N; i++)
  {
        for (int j = 0; j <= 1; j++) for (int l = 0; l <= 1; l++) dist[i][j][l] = -1;
    }

    dist[p][0][0] = 0;
    dist[p][1][1] = 0;
    dfs(p, 0, 0);
    dfs(p, 1, 1);



  for(int i=0; i<Q; i++)
  {
    int sum = 0;
    int cdist = G[i];
    for (int j = 0; j < n; j++)
    {
        //if (i == 0) cout << "a " << onCycle[p][0]<< " " << onCycle[p][1] << " " << dist[j][0][0] << " " << dist[j][0][1] << " " << j <<  endl;
        for (int k = 0; k <= 1; k++)
        {
            if (dist[j][0][k] != -1)
            {
                if (dist[j][0][k] == cdist) sum++;
                else if (onCycle[p][k] && cdist > dist[j][0][k] && dist[j][0][k] % onCycle[p][k] == cdist % onCycle[p][k])
                {
                    sum++;
                }
            }
        }
    }
      answer(sum);
  }
}

/*
4 4 0
1 2
2 3
3 1
0 1
20
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1

*/

컴파일 시 표준 에러 (stderr) 메시지

garden.cpp: In function 'void dfs(int, int, int)':
garden.cpp:19:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |     for (int i = 0; i < adj[node].size(); i++)
      |                     ~~^~~~~~~~~~~~~~~~~~

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