oj.uz

Submission #42449

# Submission time Handle Problem Language Result Execution time Memory
42449 2018-02-27T09:58:51 Z ruhanhabib39 Amusement Park (JOI17_amusement_park) C++14
10 / 100
 52 ms 13888 KB 
#include "Joi.h"
#include <vector>
#include <algorithm>
#include <set>

using std::set;
using std::vector;
using std::fill;

namespace {
   const int MAXN = 1e4;

   int N;
   long long X;
   set<int> G[MAXN + 10];
   bool vis[MAXN + 10];

   long long ii = 0;
   void dfs(int u) {
      if(vis[u]) return;

      MessageBoard(u, bool(X & (1LL << ii)));
      vis[u] = true;
      ii = (ii + 1) % 60;
      
      for(int v : G[u]) {
         dfs(v);
      }
   }
};

void Joi(int N_, int M, int A[], int B[], long long X_, int T) {
   N = N_; X = X_;
   fill(G, G + N, set<int>());
   for(int i = 0; i < M; i++) {
      G[A[i]].insert(B[i]);
      G[B[i]].insert(A[i]);
   }
   fill(vis, vis + N, 0); ii = 0;
   dfs(0);
}

#include "Ioi.h"
#include <vector>
#include <algorithm>
#include <iostream>
#include <set>

using std::vector;
using std::fill;
using std::set;

namespace {
   const int MAXN = 1e4;

   int N;
   set<int> G[MAXN + 10];
   int pos[MAXN + 10];
   
   set<int> child[MAXN + 10];
   int par[MAXN + 10];

   long long res[60 + 10];

   int ii = 0;
   void dfs(int u) {
      pos[u] = ii;
      ii = (ii + 1) % 60;
      for(int v : G[u]) {
         if(pos[v] != -1) continue;
         par[v] = u;
         child[u].insert(v);
         dfs(v);
      }
   }

   long long solve(int u) {
      for(int cc = 0; cc < 120 && (child[u].size() || par[u] != -1); cc++) {
         //std::cerr << "par[" << u << "] = " << par[u] << "\n";
         //std::cerr << "child[" << u << "] = [";
         //for(int v : child[u]) std::cerr << " " << v;
         //std::cerr << "]\n";
         if(!child[u].size()) {
            res[pos[par[u]]] = Move(par[u]);
            child[par[u]].erase(u);
            u = par[u];
         } else {
            int v = *child[u].begin(); child[u].erase(child[u].begin());
            res[pos[v]] = Move(v);
            u = v;
            
         }
      }
      long long X = 0;
      for(long long i = 0; i < 60; i++) {
         X |= res[i] << i;
         //std::cerr << res[i] << " ";
      }
      //std::cerr << "\n";
      //std::cerr << "X = " << X << "\n";
      return X;
   }

   long long work(int S, int V) {
      res[pos[S]] = V;
      return solve(S);
   }
};

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]].insert(B[i]);
      G[B[i]].insert(A[i]);
   }
   fill(pos, pos + N, -1);
   fill(res, res + 60, -1);
   fill(par, par + N, -1);
   fill(child, child + N, set<int>());
   par[0] = -1; dfs(0);
   return work(P, V);
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2140 KB Output is correct
2 Correct 4 ms 2768 KB Output is correct
3 Incorrect 5 ms 2920 KB Wrong Answer [7]
4 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 8756 KB Output is correct
2 Correct 41 ms 10056 KB Output is correct
3 Incorrect 48 ms 10288 KB Wrong Answer [7]
4 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 10472 KB Output is correct
2 Correct 4 ms 10472 KB Output is correct
3 Correct 4 ms 10472 KB Output is correct
4 Correct 6 ms 10472 KB Output is correct
5 Correct 7 ms 10472 KB Output is correct
6 Correct 6 ms 10472 KB Output is correct
7 Correct 7 ms 10472 KB Output is correct
8 Correct 6 ms 10472 KB Output is correct
9 Correct 17 ms 10472 KB Output is correct
10 Correct 18 ms 10472 KB Output is correct
11 Correct 17 ms 10472 KB Output is correct
12 Correct 4 ms 10472 KB Output is correct
13 Correct 4 ms 10472 KB Output is correct
14 Correct 4 ms 10472 KB Output is correct
15 Correct 4 ms 10472 KB Output is correct

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 10492 KB Output is correct
2 Correct 41 ms 10864 KB Output is correct
3 Correct 44 ms 11400 KB Output is correct
4 Correct 22 ms 11584 KB Output is correct
5 Correct 23 ms 11584 KB Output is correct
6 Correct 37 ms 11584 KB Output is correct
7 Correct 23 ms 11584 KB Output is correct
8 Correct 33 ms 11584 KB Output is correct
9 Correct 22 ms 11584 KB Output is correct
10 Correct 29 ms 11584 KB Output is correct
11 Correct 32 ms 11584 KB Output is correct
12 Correct 22 ms 11584 KB Output is correct
13 Correct 27 ms 11584 KB Output is correct
14 Correct 20 ms 11584 KB Output is correct
15 Incorrect 28 ms 11584 KB Wrong Answer [7]
16 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 12604 KB Output is correct
2 Correct 48 ms 13756 KB Output is correct
3 Correct 52 ms 13888 KB Output is correct
4 Incorrect 25 ms 13888 KB Wrong Answer [7]
5 Halted 0 ms 0 KB -