Submission #347390

#	Time	Username	Problem	Language	Result	Execution time	Memory
347390		idk321	Tropical Garden (IOI11_garden)	C++11	49 / 100	4 ms	1388 KiB

garden

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

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int N = 1001;
const int K = 101;
vector<int> adj[N];
int dp[N][K][2];
int best[N][2];


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


  for (int i = 0; i < m; i++)
  {
    for (int j = 0; j <= 1; j++)
    {
        if (best[R[i][j]][0] == 0) best[R[i][j]][0] = i + 1;
        else if (best[R[i][j]][1] == 0) best[R[i][j]][1] = i + 1;
    }
    adj[R[i][0]].push_back(R[i][1]);
    adj[R[i][1]].push_back(R[i][0]);
  }

  dp[p][0][0] = 1;
  dp[p][0][1] = 1;
  for (int i = 1; i < K; i++)
  {
    for (int j = 0; j < n; j++)
    {
        int other = adj[j][0];
        //if (j == 2) cout << best[j][0] << " " << best[other][0] << endl;
        if (best[j][0] == best[other][0] && best[other][1] != 0)
        {
            dp[j][i][0] = dp[other][i - 1][1];
        } else
        {
            dp[j][i][0] = dp[other][i - 1][0];
        }
        if (adj[j].size() > 1)
        {
            other = adj[j][1];
            if (best[j][1] == best[other][0] && best[other][1] != 0)
            {
                dp[j][i][1] = dp[other][i - 1][1];
            } else
            {
                dp[j][i][1] = dp[other][i - 1][0];
            }
        }
    }
  }



  for(int i=0; i<Q; i++)
  {
    int sum = 0;
    int dist = G[i];
    for (int j = 0; j < n; j++) sum += dp[j][dist][0];
      answer(sum);
  }
}

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