oj.uz

답안 #202597

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
202597 2020-02-17T08:58:37 Z rdd6584 Lampice (COCI19_lampice) C++14
42 / 110
 1066 ms 11304 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[50001];
int rotn[50001];
char visit[50001];
char s[50001];
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 5 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 794 ms 9768 KB Output is correct
2 Correct 860 ms 9836 KB Output is correct
3 Correct 811 ms 9892 KB Output is correct
4 Correct 861 ms 10284 KB Output is correct
5 Correct 902 ms 11304 KB Output is correct
6 Correct 555 ms 9592 KB Output is correct

Subtask #3
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1066 ms 7592 KB Output is correct
2 Correct 975 ms 7304 KB Output is correct
3 Correct 1006 ms 7824 KB Output is correct
4 Incorrect 651 ms 7152 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 5 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 794 ms 9768 KB Output is correct
9 Correct 860 ms 9836 KB Output is correct
10 Correct 811 ms 9892 KB Output is correct
11 Correct 861 ms 10284 KB Output is correct
12 Correct 902 ms 11304 KB Output is correct
13 Correct 555 ms 9592 KB Output is correct
14 Correct 1066 ms 7592 KB Output is correct
15 Correct 975 ms 7304 KB Output is correct
16 Correct 1006 ms 7824 KB Output is correct
17 Incorrect 651 ms 7152 KB Output isn't correct
18 Halted 0 ms 0 KB -