oj.uz

답안 #202595

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
202595 2020-02-17T08:54:08 Z rdd6584 Lampice (COCI19_lampice) C++14
42 / 110
 1036 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, len;

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 + hb * pr[1]]--;

    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];

    auto t = um.find(ha + hb * pr[1]);
    um[ha + hb * pr[1]]++;

    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 + hb * pr[1]);
        // 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 'void pcal(int, int, int, int, int)':
lampice.cpp:67:10: warning: variable 't' set but not used [-Wunused-but-set-variable]
     auto t = um.find(ha + hb * pr[1]);
          ^
lampice.cpp: In function 'int main()':
lampice.cpp:169:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
lampice.cpp:170:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%s", s);
     ~~~~~^~~~~~~~~
lampice.cpp:179: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 13 ms 1576 KB Output is correct
4 Correct 13 ms 1704 KB Output is correct
5 Correct 5 ms 1528 KB Output is correct
6 Correct 5 ms 1528 KB Output is correct
7 Correct 6 ms 1528 KB Output is correct

Subtask #2
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 842 ms 9768 KB Output is correct
2 Correct 868 ms 9896 KB Output is correct
3 Correct 802 ms 9896 KB Output is correct
4 Correct 894 ms 10428 KB Output is correct
5 Correct 943 ms 11304 KB Output is correct
6 Correct 565 ms 9464 KB Output is correct

Subtask #3
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1036 ms 7720 KB Output is correct
2 Correct 1027 ms 7332 KB Output is correct
3 Correct 975 ms 7848 KB Output is correct
4 Incorrect 617 ms 7100 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 13 ms 1576 KB Output is correct
4 Correct 13 ms 1704 KB Output is correct
5 Correct 5 ms 1528 KB Output is correct
6 Correct 5 ms 1528 KB Output is correct
7 Correct 6 ms 1528 KB Output is correct
8 Correct 842 ms 9768 KB Output is correct
9 Correct 868 ms 9896 KB Output is correct
10 Correct 802 ms 9896 KB Output is correct
11 Correct 894 ms 10428 KB Output is correct
12 Correct 943 ms 11304 KB Output is correct
13 Correct 565 ms 9464 KB Output is correct
14 Correct 1036 ms 7720 KB Output is correct
15 Correct 1027 ms 7332 KB Output is correct
16 Correct 975 ms 7848 KB Output is correct
17 Incorrect 617 ms 7100 KB Output isn't correct
18 Halted 0 ms 0 KB -