oj.uz

답안 #93960

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
93960 2019-01-13T18:37:28 Z updown1 Rima (COCI17_rima) C++17
112 / 140
 1000 ms 64348 KB 
/*
The length decreases and then increases
for every node, count everything with the same suffix
dp[node] = (increasing sequence) max length sequence starting from this node ( but not counting count[node] or this node )
try every length as the smallest length
answer is max(big1[len]+big2[len]+count[word] where big1 an big2 have the same suffix,
             1 + big1 + big2 + count[word])
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define For(i, a, b) for(int i=a; i<b; i++)
#define ffi For(i, 0, N)
#define ffj For(j, 0, M)
#define ffa ffi ffj
#define s <<" "<<
#define c <<" : "<<
#define w cout
#define e "\n"
#define pb push_back
#define mp make_pair
#define a first
#define b second
//#define int ll
const int MAXN=500000, INF=1000000000;
///500,000,000
int N, dp[MAXN], out;
string inp[MAXN];
bool vis[MAXN];
map<string, vector<int> > cnt; /// (suffix, vector<index> )

void go(int at) {
    if (vis[at]) return;
    vis[at] = true;
    for (int i: cnt[inp[at]]) {
        go(i);
        dp[at] = max(dp[at], dp[i]+(int)cnt[inp[at]].size());
    }
    //w<< inp[at] s (int)(cnt[inp[at]].size())<<e;
}

main() {
    //ifstream cin("test.in");
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> N;
	ffi {
	    cin >> inp[i];
	    cnt[inp[i].substr(1)].pb(i);
	}
	ffi go(i);
	//ffi w<< inp[i] c dp[i]<<e;
	ffi vis[i] = false;
	ffi if (!vis[i]) {
        string use = inp[i].substr(1);
        int big1 = 0, big2 = 0;
        for (int j: cnt[use]) {
            big2 = max(big2, dp[j]);
            if (big2 > big1) swap(big2, big1);
            vis[j] = true;
        }
        out = max(out, big1+big2+(int)cnt[use].size());
        if (cnt[use].size() == 1) {
            big1 = big2 = 0;
            for (int j: cnt[inp[i]]) {
                big2 = max(big2, dp[j]);
                if (big2 > big1) swap(big2, big1);
            }
            //if (i == 3) w<< big1 s big2 s (int)cnt[inp[i]].size()<<e;
            out = max(out, 1+big1+big2+(int)cnt[inp[i]].size());
        }
	}
	w<< out<<e;
}

Compilation message

rima.cpp:42:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^

Subtask #1
112.0 / 140.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 15992 KB Output is correct
2 Correct 15 ms 15992 KB Output is correct
3 Correct 15 ms 15992 KB Output is correct
4 Execution timed out 1087 ms 64348 KB Time limit exceeded
5 Correct 42 ms 22264 KB Output is correct
6 Correct 21 ms 18188 KB Output is correct
7 Incorrect 20 ms 17864 KB Output isn't correct
8 Correct 20 ms 17624 KB Output is correct
9 Correct 61 ms 24924 KB Output is correct
10 Correct 20 ms 17660 KB Output is correct