oj.uz

Submission #42455

# Submission time Handle Problem Language Result Execution time Memory
42455 2018-02-27T12:09:01 Z ruhanhabib39 Amusement Park (JOI17_amusement_park) C++14
0 / 100
 3000 ms 524288 KB 
#include "Joi.h"
#include <bits/stdc++.h>
using namespace std;

namespace {
   const int MAXN = 1e4;

   int N;
   vector<int> G[MAXN + 10];

   vector<int> tree[MAXN + 10];
   bool vis[MAXN + 10];

   vector<int> subtree[MAXN + 10];
   long long pos[MAXN + 10];

   void mst(int u) {
      vis[u] = true;
      for(int v : G[u]) {
         if(!vis[v]) {
            tree[u].push_back(v);
            tree[v].push_back(u);
            mst(v);
         }
      }
   }
   bool hasEdge(int u, int v) {
      return binary_search(tree[u].begin(), tree[u].end(), v);
   }
   void init_tree(int u, int p, vector<int>& subt) {
      if(subt.size() >= 60) return;
      pos[u] = subt.size(); subt.push_back(u);
      for(int v : tree[u]) {
         if(v != p) init_tree(v, u, subt);
      }
   }
   void work(int u, int p, vector<pair<int,int>> deg) {
      bool in = any_of(deg.begin(), deg.end(), [=](auto x) { return x.first == u; });

      if(!in) {
         auto rem = find_if(deg.begin(), deg.end(), 
            [=](auto x) { return x.first != p && x.second == -1; });

         for(auto& it : deg) {
            if(hasEdge(it.first, rem->first)) it.second--;
         }
         pos[u] = pos[rem->first];
         *rem = {u, 1};
         auto ppos = find_if(deg.begin(), deg.end(), [=](auto x) { return x.first == p; });
         ppos->second++;
      }

      for(auto it : deg) subtree[u].push_back(it.first);
      for(int v : G[u]) {
         if(v != p) work(v, u, deg);
      }
   }
   void build() {
      mst(0);
      for(int u = 1; u <= N; u++) sort(tree[u].begin(), tree[u].end());
      vector<int> subt; init_tree(0, -1, subt);
      vector<pair<int,int>> deg;
      for(int u : subt) {
         int cc = count_if(subt.begin(), subt.end(),
               [=](int v) { return hasEdge(u, v); });
         deg.emplace_back(u, cc);
      }
      work(0, -1, deg);
   }
};

void Joi(int N_, int M, int A[], int B[], long long X, int T) {
   N = N_;
   fill(G, G + N, vector<int>());
   for(int i = 0; i < M; i++) {
      G[A[i]].push_back(B[i]);
      G[B[i]].push_back(A[i]);
   }
   build();
   for(int i = 0; i < N; i++) {
      MessageBoard(i, bool(X & (1LL << pos[i])));
   }
}

#include "Ioi.h"
#include <bits/stdc++.h>
using namespace std;


namespace {
   const int MAXN = 1e4;

   int N;
   vector<int> G[MAXN + 10];

   vector<int> tree[MAXN + 10];
   bool vis[MAXN + 10];

   vector<int> subtree[MAXN + 10];
   long long pos[MAXN + 10];

   void mst(int u) {
      vis[u] = true;
      for(int v : G[u]) {
         if(!vis[v]) {
            tree[u].push_back(v);
            tree[v].push_back(u);
            mst(v);
         }
      }
   }
   bool hasEdge(int u, int v) {
      return binary_search(tree[u].begin(), tree[u].end(), v);
   }
   void init_tree(int u, int p, vector<int>& subt) {
      if(subt.size() >= 60) return;
      pos[u] = subt.size(); subt.push_back(u);
      for(int v : tree[u]) {
         if(v != p) init_tree(v, u, subt);
      }
   }
   void work(int u, int p, vector<pair<int,int>> deg) {
      bool in = any_of(deg.begin(), deg.end(), [=](auto x) { return x.first == u; });

      if(!in) {
         auto rem = find_if(deg.begin(), deg.end(), 
            [=](auto x) { return x.first != p && x.second == -1; });

         for(auto& it : deg) {
            if(hasEdge(it.first, rem->first)) it.second--;
         }
         pos[u] = pos[rem->first];
         *rem = {u, 1};
         auto ppos = find_if(deg.begin(), deg.end(), [=](auto x) { return x.first == p; });
         ppos->second++;
      }

      for(auto it : deg) subtree[u].push_back(it.first);
      for(int v : G[u]) {
         if(v != p) work(v, u, deg);
      }
   }
   void build() {
      mst(0);
      for(int u = 1; u <= N; u++) sort(tree[u].begin(), tree[u].end());
      vector<int> subt; init_tree(0, -1, subt);
      vector<pair<int,int>> deg;
      for(int u : subt) {
         int cc = count_if(subt.begin(), subt.end(),
               [=](int v) { return hasEdge(u, v); });
         deg.emplace_back(u, cc);
      }
      work(0, -1, deg);
   }
   
   int res[60]; bool good[MAXN + 10];
   void solve(int u, int p = -1) {
      for(int v : tree[u]) {
         if(good[v] && v != p) {
            res[pos[v]] = Move(v);
            solve(v, u);
         }
      }
      if(p != -1) Move(p);
   }
};

long long Ioi(int N_, int M, int A[], int B[], int P, int V, int T) {
   N = N_;
   for(int i = 0; i < M; i++) {
      G[A[i]].push_back(B[i]);
      G[B[i]].push_back(A[i]);
   }
   build();

   fill(res, res + 60, -1);
   for(int u : subtree[P]) good[u] = true;
   res[pos[P]] = V;
   solve(P);

   long long X = 0;
   for(long long i = 0; i < 60; i++) {
      X |= res[i] << i;
   }
   return X;
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 2140 KB Wrong Answer [7]
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3129 ms 262144 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 524288 KB Wrong Answer [7]
2 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3114 ms 262144 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3123 ms 262144 KB Time limit exceeded
2 Halted 0 ms 0 KB -