Submission #638225

#	Time	Username	Problem	Language	Result	Execution time	Memory
638225		iee	Lampice (COCI19_lampice)	C++17	17 / 110	284 ms	48084 KiB

lampice

// iee
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <set>
#include <map>

#define rep(i, a, b) for (auto i = (a); i <= (b); ++i)
#define per(i, a, b) for (auto i = (a); i >= (b); --i)
#define fi first
#define se second
using ll = long long;
using ull = unsigned long long;
using namespace std;
void work(int);

template <class T> void read(T &x) {
  x = 0; int f = 1, ch = getchar();
  while (!isdigit(ch)) { if (ch == '-') f = -1; ch = getchar(); }
  while (isdigit(ch)) x = x * 10 + (ch - '0'), ch = getchar();
  x *= f;
}

int main() {
  int TT = 1; // cin >> TT;
  rep(CAS, 1, TT)
    work(CAS);
  return 0;
}
const int N = 5e4 + 5;
int n, u[N], v[N];
char a[N];
namespace bf {
const int N = 3005, base = 31;
vector<int> e[N];
ull hpath[N][N];
void dfs1(const int &rt, int u, int pr, ull h) {
  h = h * base + (a[u] - 'a' + 1);
  hpath[rt][u] = h;
  for (int v: e[u]) if (v != pr)
    dfs1(rt, v, u, h);
}
int ans, st[N], top;
void dfs2(const int &rt, int u, int pr) {
  st[++top] = u;
  if (top % 2 == 0 && hpath[rt][st[top / 2]] == hpath[u][st[top / 2 + 1]] || top % 2 == 1 && hpath[rt][st[top / 2 + 1]] == hpath[u][st[top / 2 + 1]]) ans = max(ans, top);
  for (int v: e[u]) if (v != pr)
    dfs2(rt, v, u);
  --top;
}
void work() {
  rep(i, 1, n - 1) e[::u[i]].push_back(::v[i]), e[::v[i]].push_back(::u[i]);
  rep(i, 1, n) dfs1(i, i, -1, 0ull);
  rep(i, 1, n) top = 0, dfs2(i, i, 0);
  cout << ans;
}

}

namespace lian {
void work() {
  
}
}

void work(int CASE) {
  scanf("%d%s", &n, a + 1);
  rep(i, 1, n - 1) scanf("%d%d", u + i, v + i);
  if (n <= 3000) { bf::work(); return; }
  lian::work();
}

Compilation message (stderr)

lampice.cpp: In function 'void bf::dfs2(const int&, int, int)':
lampice.cpp:48:20: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   48 |   if (top % 2 == 0 && hpath[rt][st[top / 2]] == hpath[u][st[top / 2 + 1]] || top % 2 == 1 && hpath[rt][st[top / 2 + 1]] == hpath[u][st[top / 2 + 1]]) ans = max(ans, top);
      |       ~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
lampice.cpp: In function 'void work(int)':
lampice.cpp:69:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   69 |   scanf("%d%s", &n, a + 1);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~
lampice.cpp:70:25: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   70 |   rep(i, 1, n - 1) scanf("%d%d", u + i, v + i);
      |                    ~~~~~^~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 17 / 17
• Subtask 2: 0 / 25
• Subtask 3: 0 / 31
• Subtask 4: 0 / 37