oj.uz

답안 #202594

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
202594 2020-02-17T08:49:09 Z detaomega Lampice (COCI19_lampice) C++14
0 / 110
 5000 ms 14184 KB 
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define IOS ios::sync_with_stdio(0);cin.tie(0);
#define de(x,y) cout<<#x<<" :"<<x<<y;
#define int long long
#define SZ(xx) ((int)xx.size())
#define lowbit(xx) (xx&(-xx))
#define pb push_back
typedef pair<int,int> pii;

const int maxn = 4e5+5;
int arr[maxn], ans = 0;
vector<int> vt, G[maxn]; 
double start;
bool check() {
	vector<int> rvt = vt;
	reverse(rvt.begin(), rvt.end());
	for(int i=0; i<vt.size(); i++) {
		if(vt[i]^rvt[i])
			return 0;
	}
	return 1;
}

void dfs(int now,int fa) {
	vt.push_back(arr[now]);
	if(check())
		ans = max(ans, SZ(vt));
	for(int k:G[now])
		if(k != fa)
			dfs(k, now);
	vt.pop_back();
	if((clock()-start)/CLOCKS_PER_SEC>4.9) {
		cout << ans << "\n";
		exit(0);
	}
}

void solve() {
	string s;  
        cin >> s;  
        int ans = 1 , len = s.size();  
        for(int i=0;i<s.size()-1;i++) {  
            int tmp = 1;  
            for(int j=1;j<=s.size();j++) {  
                if(i-j < 0 || i+j >= len)   
                    break;  
                if(s[i - j] != s[i + j])  
                    break;  
                tmp += 2;  
            }  
            ans = max(ans , tmp);  
            if(s[i] == s[i+1]) {  
                tmp = 2;  
                for(int j=1;j<=s.size();j++) {  
                if(i-j < 0 || i+j+1 >= len)   
                    break;  
                if(s[i - j] != s[i + j+1])  
                    break;  
                tmp += 2;  
                }  
            }  
            ans = max(ans , tmp);  
            if(ans == len)  
                break;  
        }  
        cout << ans << "\n";  
}

main() {
IOS
	start = clock();
	
	mt19937 mt_rand(time(0));
	double start=clock();
	int n;
	cin >> n; 
	for(int i=1; i<=n; i++) {
		char c;
		cin >> c;
		arr[i] = c - 'a';
	}
	for(int i=1; i<n; i++) {
		int u, v;
		cin >> u >> v;
		G[u].push_back(v);
		G[v].push_back(u); 
	}
	for(int i=n; i>=1; i--) {
		dfs(rand() % n + 1, 0);
	}
	cout << ans << "\n";
	
	




}

Compilation message

lampice.cpp: In function 'bool check()':
lampice.cpp:21:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<vt.size(); i++) {
               ~^~~~~~~~~~
lampice.cpp: In function 'void solve()':
lampice.cpp:46:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=0;i<s.size()-1;i++) {  
                     ~^~~~~~~~~~~
lampice.cpp:48:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int j=1;j<=s.size();j++) {  
                         ~^~~~~~~~~~
lampice.cpp:58:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 for(int j=1;j<=s.size();j++) {  
                             ~^~~~~~~~~~
lampice.cpp: At global scope:
lampice.cpp:73:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^
lampice.cpp: In function 'int main()':
lampice.cpp:78:9: warning: unused variable 'start' [-Wunused-variable]
  double start=clock();
         ^~~~~

Subtask #1
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 74 ms 9720 KB Output is correct
2 Correct 319 ms 9720 KB Output is correct
3 Incorrect 1312 ms 9976 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 5047 ms 14184 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

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

Subtask #4
0 / 37.0

# 결과 실행 시간 메모리 Grader output
1 Correct 74 ms 9720 KB Output is correct
2 Correct 319 ms 9720 KB Output is correct
3 Incorrect 1312 ms 9976 KB Output isn't correct
4 Halted 0 ms 0 KB -