oj.uz

답안 #253822

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
253822 2020-07-28T18:42:48 Z Bruteforceman Lampice (COCI19_lampice) C++11
17 / 110
 5000 ms 10776 KB 
#include <bits/stdc++.h>
using namespace std;
const int maxn = 5e4 + 5;
const int mod = 1e9 + 7;
const int base = 50021;
vector <int> g[maxn];
long long power[maxn], up[maxn], down[maxn];
int sub[maxn], dep[maxn];
bool vis[maxn];
char s[maxn];
 
void subtree(int x, int par) {
  sub[x] = 1;
  for(int i : g[x]) {
    if(vis[i]) continue;
    if(i != par) {
      subtree(i, x);
      sub[x] += sub[i];
    }
  }
}
int centroid(int x, int par, int range) {
  for(int i : g[x]) {
    if(vis[i]) continue;
    if(i != par && sub[i] > range) {
      return centroid(i, x, range);
    }
  }
  return x;
}
void dfs(int x, int par) {
  for(int i : g[x]) {
    if(vis[i]) continue;
    if(i != par) {
      dep[i] = 1 + dep[x];
      down[i] = (down[x] * base + s[i]) % mod;
      up[i] = (power[dep[i]] * s[i] + up[x]) % mod;
      dfs(i, x);
    }
  }
}
void getNode(int x, int par, vector <int> &node) {
  node.push_back(x);
  for(auto i : g[x]) {
    if(!vis[i] && i != par) {
      getNode(i, x, node);
    }
  }
}
int getHash(int dep, long long h) {
  return (h * base + dep) % mod;
}
bool solve(int x, int k) {
  subtree(x, 0);
  x = centroid(x, 0, sub[x] / 2);
  dep[x] = 0;
  up[x] = down[x] = s[x];
  dfs(x, 0);
  bool ans = false;
  unordered_set <int> table;
  for(int i : g[x]) {
    if(vis[i]) continue;
    vector <int> node, cont;
    getNode(i, x, node);
    for(auto j : node) {
      if(dep[j] + 1 == k) {
        ans |= (down[j] == up[j]);    
      } else if (dep[j] < k) {
        long long value = (up[j] * power[k - dep[j] - 1] - down[j] + power[dep[j]] * s[x] + mod) % mod;
        ans |= table.find(getHash(k - dep[j] - 1, value)) != table.end();
        cont.emplace_back(getHash(dep[j], value));
      }
    }
    for(auto j : cont) table.insert(j);
  }
  vis[x] = true;
  for(int i : g[x]) {
    if(vis[i]) continue;
    ans |= solve(i, k);
  }
  return ans;
}
 
int main() {
  int n;
  scanf("%d", &n);
  scanf("%s", s + 1);
  power[0] = 1;
  for(int i = 1; i <= n; i++) {
    power[i] = (power[i - 1] * base) % mod;
  }
  for(int i = 1; i < n; i++) {
    int p, q;
    scanf("%d %d", &p, &q);
    g[p].push_back(q);
    g[q].push_back(p);
  }
  
 
 
 
  int ans;
  int l = 1, r = (n + 1) / 2;
  while(l < r) {
    int mid = (l + r + 1) >> 1;
    memset(vis, false, sizeof vis);
    if(solve(1, 2 * mid - 1)) {
      l = mid;
    } else {
      r = mid - 1;
    }
  }
  ans = 2 * l - 1;
  l = 0; r = (n / 2);
  while(l < r) {
    int mid = (l + r + 1) >> 1;
    memset(vis, false, sizeof vis);
    if(solve(1, mid * 2)) {
      l = mid;
    } else {
      r = mid - 1;
    }
  }
  ans = max(ans, l * 2);
  printf("%d\n", ans);
  return 0;
}

Compilation message

lampice.cpp: In function 'int main()':
lampice.cpp:86:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &n);
   ~~~~~^~~~~~~~~~
lampice.cpp:87:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s", s + 1);
   ~~~~~^~~~~~~~~~~~~
lampice.cpp:94:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &p, &q);
     ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 1536 KB Output is correct
2 Correct 15 ms 1664 KB Output is correct
3 Correct 87 ms 1792 KB Output is correct
4 Correct 74 ms 1792 KB Output is correct
5 Correct 1 ms 1536 KB Output is correct
6 Correct 1 ms 1536 KB Output is correct
7 Correct 1 ms 1408 KB Output is correct

Subtask #2
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3591 ms 10776 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 5073 ms 8964 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 37.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 1536 KB Output is correct
2 Correct 15 ms 1664 KB Output is correct
3 Correct 87 ms 1792 KB Output is correct
4 Correct 74 ms 1792 KB Output is correct
5 Correct 1 ms 1536 KB Output is correct
6 Correct 1 ms 1536 KB Output is correct
7 Correct 1 ms 1408 KB Output is correct
8 Incorrect 3591 ms 10776 KB Output isn't correct
9 Halted 0 ms 0 KB -