oj.uz

답안 #202599

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
202599 2020-02-17T09:02:39 Z rdd6584 Lampice (COCI19_lampice) C++14
42 / 110
 1065 ms 11308 KB 
#include <bits/stdc++.h>
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
using namespace std;

typedef long long ll;
typedef unsigned long long llu;
typedef pair<int, int> pii;
typedef pair<int, pii> piii;
typedef pair<ll, ll> pll;
typedef pair<ll, int> pli;
typedef pair<int, ll> pil;
typedef pair<string, int> psi;
typedef pair<char, int> pci;
typedef pair<int, char> pic;
const long double PI = 3.141592653589793238462643383279502884197;

int n;
const int B = 128;
const ll pr[2] = { 1000000009, 1000000021 };
ll rhq[50002][2];

vector<int> v[50002];
int rotn[50002];
char visit[50002];
char s[50002];
int flag = 0;

int cent(int o, int pa, int cap) {
    for (int i : v[o])
        if (i != pa && !visit[i] && rotn[i] > cap)
            return cent(i, o, cap);
    return o;
}

int pre(int o, int pa) {
    int ret = 1;
    for (int i : v[o])
        if (i != pa && !visit[i])
            ret += pre(i, o);

    return rotn[o] = ret;
}

unordered_map<ll, int> um; // 개수만으로 바꿔줘도 됨.

void mcal(int o, int pa, int di, int h1, int h2) {
    h1 = (h1 + rhq[di][0] * s[o]) % pr[0];
    h2 = (h2 + rhq[di][1] * s[o]) % pr[1]; // 경로 길이 반환..

    int ha = h1 * rhq[n - di][0] % pr[0];  // 끝의 높이를 n에 맞춰줌
    int hb = h2 * rhq[n - di][1] % pr[1];
    um[ha * pr[1] + hb]--;

    for (int i : v[o])
        if (i != pa && !visit[i])
            mcal(i, o, di + 1, h1, h2);
}

void pcal(int o, int pa, int di, int h1, int h2) {
    h1 = (h1 + rhq[di][0] * s[o]) % pr[0];
    h2 = (h2 + rhq[di][1] * s[o]) % pr[1]; // 경로 길이 반환..

    int ha = h1 * rhq[n - di][0] % pr[0];  // 끝의 높이를 n에 맞춰줌
    int hb = h2 * rhq[n - di][1] % pr[1];
    um[ha * pr[1] + hb]++;

    for (int i : v[o])
        if (i != pa && !visit[i])
            pcal(i, o, di + 1, h1, h2);
}

// 당겨야 함.. 길이가 얼만큼인지 아니까..
// 계산할 때, 위치 정규화 시켜줘야 함.
// dd는 문자열 시작점의 높이
// 큐에서 가장 최근 문자를 뺀다
deque<char> dq;

void cal(int o, int pa, int di, int dd, int h1, int h2, int r1, int r2, int s1, int s2) {
    h1 = (h1 + rhq[di][0] * s[o]) % pr[0];
    h2 = (h2 + rhq[di][1] * s[o]) % pr[1];
    dq.push_back(s[o]);

    int ha, hb;

    // dd까지 들어가 있다.. 그러니까 이제 뺏을 차례인 곳임.
    // can이면 dd만큼 더함.
    // 항상 같다는 전제니까 dd-di+1
    vector<char> rev;
    while (dd <= di) {
        ha = (h1 - s1 + pr[0]) % pr[0];
        hb = (h2 - s2 + pr[1]) % pr[1];

        // printf("befo %d %d ha hb//\n", ha, hb);

        ha = ha * rhq[n - di][0] % pr[0];
        hb = hb * rhq[n - di][1] % pr[1];
        auto t = um.find(ha * pr[1] + hb);
        // printf("%c %d %d ha hb//\n", s[o], ha, hb);

        if (dd == 0 || t == um.end() || t->second <= 0) {
            char w = dq.front();
            dq.pop_front();
            rev.push_back(w); // 역순으로 프론트에 넣어준다.

            r1 = (r1 + rhq[n - dd][0] * w) % pr[0];
            r2 = (r2 + rhq[n - dd][1] * w) % pr[1];

            s1 = (s1 + rhq[dd][0] * w) % pr[0];
            s2 = (s2 + rhq[dd][1] * w) % pr[1];

            dd++;
        }
        else break;
    }

    int sa = s1 * rhq[n - (dd - 1)][0] % pr[0];
    int sb = s2 * rhq[n - (dd - 1)][1] % pr[1];

    // printf("di : %d, dd : %d\n", di, dd);
    if (r1 == sa && r2 == sb) {
       // printf("%d %d // %d :pass\n", di, dd, (di - dd + 1) * 2 + dd);
        flag = max(flag, (di - dd + 1) * 2 + dd);
    }

    for (int i : v[o])
        if (i != pa && !visit[i]) {
            if (o == pa) mcal(i, o, 1, 0, 0);
            cal(i, o, di + 1, dd, h1, h2, r1, r2, s1, s2);
            if (o == pa) pcal(i, o, 1, 0, 0);
        }

    while (!rev.empty()) {
        dq.push_front(rev.back());
        rev.pop_back();
    }

    dq.pop_back();
}

// o가 포함된 센트로이드를 찾아라.
// 이제 센트로이드에서 구해야하는데..
// 해싱을 잘 써야함.
// 이분탐색시 초기화 잘해줘야함

void go(int o) {
    pre(o, o);
    int t = cent(o, o, rotn[o] / 2);
    visit[t]++;

    // printf("%d %d\n", o, t);

    pcal(t, t, 0, -s[t], -s[t]);
    cal(t, t, 0, 0, 0, 0, 0, 0, 0, 0);
    dq.clear();
    um.clear();
    // printf("//%d//\n", flag);

    for (int i : v[t])
        if (!visit[i])
            go(i);

    visit[t]--;
}

int main() {
    scanf("%d", &n);
    scanf("%s", s);

    rhq[0][0] = rhq[0][1] = 1;
    for (int i = 1; i <= n; i++)
        for (int j = 0; j < 2; j++)
            rhq[i][j] = rhq[i - 1][j] * B % pr[j];

    for (int i = 0; i < n - 1; i++) {
        int a, b;
        scanf("%d %d", &a, &b);
        a--; b--;
        v[a].push_back(b);
        v[b].push_back(a);
    }

    // 훌수팰린.
    // 길이= mid * 2 + 1

    /*
    int l = 0, r = (n - 1) / 2, mid;
    int ans = 0;
    while (l <= r) {
        mid = (l + r) / 2;
        flag = 0, len = mid * 2 + 1;

        go(0);
        if (flag) l = mid + 1;
        else r = mid - 1;
    }
    ans = max(ans, l * 2 + 1);

    l = 0, r = n / 2;
    while (l <= r) {
        mid = (l + r) / 2;
        flag = 0, len = mid * 2;

        go(0);
        if (flag) l = mid + 1;
        else r = mid - 1;
    }
    ans = max(ans, l * 2);
    printf("%d", ans);
    */

    go(0);
    printf("%d", flag);
}

Compilation message

lampice.cpp: In function 'int main()':
lampice.cpp:167:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
lampice.cpp:168:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%s", s);
     ~~~~~^~~~~~~~~
lampice.cpp:177:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &a, &b);
         ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 1528 KB Output is correct
2 Correct 7 ms 1528 KB Output is correct
3 Correct 11 ms 1656 KB Output is correct
4 Correct 13 ms 1656 KB Output is correct
5 Correct 6 ms 1528 KB Output is correct
6 Correct 5 ms 1528 KB Output is correct
7 Correct 5 ms 1528 KB Output is correct

Subtask #2
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 834 ms 9788 KB Output is correct
2 Correct 814 ms 9768 KB Output is correct
3 Correct 817 ms 10008 KB Output is correct
4 Correct 868 ms 10280 KB Output is correct
5 Correct 917 ms 11308 KB Output is correct
6 Correct 546 ms 9592 KB Output is correct

Subtask #3
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1065 ms 7592 KB Output is correct
2 Correct 1022 ms 7336 KB Output is correct
3 Correct 1014 ms 7848 KB Output is correct
4 Incorrect 665 ms 7280 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 37.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 1528 KB Output is correct
2 Correct 7 ms 1528 KB Output is correct
3 Correct 11 ms 1656 KB Output is correct
4 Correct 13 ms 1656 KB Output is correct
5 Correct 6 ms 1528 KB Output is correct
6 Correct 5 ms 1528 KB Output is correct
7 Correct 5 ms 1528 KB Output is correct
8 Correct 834 ms 9788 KB Output is correct
9 Correct 814 ms 9768 KB Output is correct
10 Correct 817 ms 10008 KB Output is correct
11 Correct 868 ms 10280 KB Output is correct
12 Correct 917 ms 11308 KB Output is correct
13 Correct 546 ms 9592 KB Output is correct
14 Correct 1065 ms 7592 KB Output is correct
15 Correct 1022 ms 7336 KB Output is correct
16 Correct 1014 ms 7848 KB Output is correct
17 Incorrect 665 ms 7280 KB Output isn't correct
18 Halted 0 ms 0 KB -