oj.uz

답안 #223418

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
223418 2020-04-15T08:58:34 Z errorgorn Lampice (COCI19_lampice) C++14
25 / 110
 28 ms 35968 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ii pair<ll,ll>
#define iii pair<ll,ii>
#define endl '\n'

const int INF=1000000000;

int edges[300005][26];
int backedge[300005];
int len[300005];

int PREV=0;
int INDEX=1;

int n;
string s;

vector<int> al[3005];
int parent[3005][15];
int level[3005]; //depth idk why i used to call it level

int in[3005];
int out[3005];

int DFS_TIME=0;

void dfs(int i,int p){
	in[i]=++DFS_TIME;
    int curr;
    for (auto it=al[i].begin();it!=al[i].end();it++){
        if (*it==p) continue;
        level[*it]=level[i]+1;
        parent[*it][0]=i;
        curr=i;
        for (int x=0;parent[curr][x]!=-1;x++){
            curr=parent[*it][x+1]=parent[curr][x];
        }
        dfs(*it,i);
    }
    out[i]=DFS_TIME;
}

int mov(int i,int j){
    for (int x=0;x<22;x++){
        if (j&1){
            i=parent[i][x];
        }
        j>>=1;
    }
    return i;
}

int lca(int i,int j){
    if (level[i]<level[j]) swap(i,j);
    i=mov(i,level[i]-level[j]);
    if (i==j) return i;
    for (int x=21;x>=0;x--){
        if (parent[i][x]!=parent[j][x]){
            i=parent[i][x];
            j=parent[j][x];
        }
    }
    return parent[i][0];
}

int dist(int i,int j){
    return level[i]+level[j]-2*level[lca(i,j)];
}


int memo[3005][3005];

int dp(int i,int j){
	if (memo[i][j]!=-1) return memo[i][j];
	
	if (s[i]!=s[j]) return -INF;
	
	if (level[i]>level[j]) swap(i,j); //i could be ancestor of j
	if (i==j) return memo[i][j]=1;
	else if (parent[j][0]==i) return memo[i][j]=2;
	else{
		if (in[i]<=in[j] && out[j]<=out[j]){
			return dp(mov(j,level[j]-level[i]-1),parent[j][0])+2;
		}
		else{
			return dp(parent[i][0],parent[j][0])+2;
		}
	}
}

int main(){
	ios::sync_with_stdio(0);
    cin.tie(0);
	
	cin>>n>>s;
	
	if (n<=3000){
		int a,b;
		for (int x=1;x<n;x++){
			cin>>a>>b;
			a--,b--;
			al[a].push_back(b);
			al[b].push_back(a);
		}
		
		memset(parent,-1,sizeof(parent));
		dfs(0,-1);


		int ans=0;
		
		memset(memo,-1,sizeof(memo));
		for (int x=0;x<n;x++)
			for (int y=0;y<n;y++)
				ans=max(ans,dp(x,y));
				
		cout<<ans<<endl;
	}
	else{
		int ans=0;
		
		memset(edges,-1,sizeof(edges));
		backedge[0]=0,backedge[1]=0;
		len[0]=-1,len[1]=0;

		for (int x=0;x<s.size();x++){
			while (s[x-len[PREV]-1]!=s[x]) 
				PREV=backedge[PREV];
			
			if (edges[PREV][s[x]-'a']==-1) 
				edges[PREV][s[x]-'a']=++INDEX;
			int curr=edges[PREV][s[x]-'a'];
			len[curr]=len[PREV]+2;
			
			ans=max(ans,len[curr]);
			
			if (len[curr]==1){
				backedge[curr]=1;
			}
			else{
				int b=backedge[PREV];
				while (s[x-len[b]-1]!=s[x]) b=backedge[b];
				backedge[curr]=edges[b][s[x]-'a'];
			}
			
			PREV=curr;
		}
		
		cout<<ans<<endl;
	}
}

Compilation message

lampice.cpp: In function 'int dp(int, int)':
lampice.cpp:84:29: warning: self-comparison always evaluates to true [-Wtautological-compare]
   if (in[i]<=in[j] && out[j]<=out[j]){
                       ~~~~~~^~~~~~~~
lampice.cpp: In function 'int main()':
lampice.cpp:128:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int x=0;x<s.size();x++){
                ~^~~~~~~~~

Subtask #1
0 / 17.0

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

Subtask #2
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 22 ms 31104 KB Output is correct
2 Correct 23 ms 31360 KB Output is correct
3 Correct 21 ms 31616 KB Output is correct
4 Correct 22 ms 31616 KB Output is correct
5 Correct 22 ms 31488 KB Output is correct
6 Correct 22 ms 31744 KB Output is correct

Subtask #3
0 / 31.0

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

Subtask #4
0 / 37.0

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