oj.uz

답안 #895896

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
895896 2023-12-31T03:51:33 Z now_or_never Lampice (COCI19_lampice) C++14
0 / 110
 5000 ms 14172 KB 
//Name: Nguyen Quang Huy
//Time: 2023-2024
#include <bits/stdc++.h>
#define Foru(i,a,b) for(int i=(a);i<=(b);++i)
#define Ford(i,a,b) for(int i=(a);i>=(b);--i)
#define se second
#define fi first
#define nl cout << "\n";
#define pi pair<int,int>
#define bit(x, k) (1ll&((x)>>(k)))
//#define sz size
#define io() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define ms(a,i) memset(a,i,sizeof(a))
#define pb(x) push_back(x)
#define epb(x,y) emplace_back({x,y})
#define all(x) (x).begin(), (x).end()
#define hr cout << "-----------------------------------------------\n";

typedef long long ll;

using namespace std;
const ll mod=1e9+7;
const int inf=0x3f3f3f3f;
const long long base=311;
const int maxn=5e4+7;

template<class T> T mi(T a, T b){return (a<=b)?a:b;}
template<class T> T ma(T a, T b){return (a>=b)?a:b;}
template<class T> void Unique(vector<T> &v){sort(all(v));v.erase(unique(all(v)), v.end());}

int n;
vector<int> g[maxn];
int sz[maxn], mxd=1, Len, ans, cc;
char a[maxn];
ll pw[maxn];
bool del[maxn], found;
unordered_map<ll,bool> mp[maxn];

void ioFile(string str){
    freopen((str+".in").c_str(),"r",stdin);
    freopen((str+".out").c_str(),"w",stdout);
}

void inp(){
    cin >> n;
    Foru(i,1,n)cin >> a[i];
    Foru(i,1,n-1){
        int u,v;cin >> u >> v;
        g[u].pb(v);
        g[v].pb(u);
    }
    pw[0]=1;
    Foru(i,1,maxn) pw[i]=(1ll*pw[i-1]*base)%mod;
}

void dfsBase(int u,int p){
    sz[u]=1;
    for(int v:g[u])if(v!=p&&!del[v]){
        dfsBase(v,u);
        sz[u]+=sz[v];
    }
}

int centroid(int u, int p, int d){
    for (int v: g[u]) if (v != p && !del[v]) {
        if ((sz[v] << 1) > n)
            return centroid(v, u, n);
    }
    return u;
}

bool dfs(int u, int p, int h, ll hd, ll hu, bool t){
    if(Len<h)return false;
    hd=(hd*1ll*base+(a[u]-'a'+1))&mod;
    hu=(hu+pw[h-1]*1ll*(a[u]-'a'+1))%mod;
    ll x=(hu*1ll*pw[Len-h]-hd+mod)%mod;
    if(t){
        if(h+1==Len&&((hu*1ll*base+(a[cc]-'a'+1))%mod==hd)){
            return true;
        }
        if(Len>h&&mp[Len-h-1].find(x)!=mp[Len-h-1].end()){
            return true;
        }
    } else {mp[h][x]=true;}
    if(Len>h){
        for(int v:g[u])if(v!=p&&!del[v]){
            mxd=max(mxd,h+1);
            if(dfs(v,u,h+1,hd,hu,t))return true;
        }
    }
    return false;
}

bool cd(int u=1){
    dfsBase(u,0);
    int r=centroid(u,0,sz[u]);
    cc=r;
    del[r]=true;
    mxd=1;

    for(int v:g[r])if(!del[v]){
        if(dfs(v,0,1,(a[r]-'a'+1),0,true))return true;
        if(dfs(v,0,1,(a[r]-'a'+1),0,false))return true;
    }

    Foru(i,0,mxd)mp[i].clear();

    for(int v:g[r])if(!del[v]){
        if(cd(v))return true;
    }
    return false;
}

bool ok(int len){
    Foru(i,0,n)mp[i].clear();
    ms(del,false);
    found=false;
    Len=len;
    return cd();
}


void solve(){
    vector<int> le,chan;
    Foru(i,1,n){
        if(i&1)le.pb(i);
        else chan.pb(i);
    }
    int ans1=0,ans2=0;
    int l=0,r=le.size()-1,mid;
    while(l<=r){
        mid=l+((r-l)>>1);
        if(ok(le[mid])){
            ans1=mid;
            l=mid+1;
        }else {r=mid-1;}
    }
    l=0;r=chan.size()-1;
    while(l<=r){
        mid=l+((r-l)>>1);
        if(ok(chan[mid])){
            ans2=mid;
            l=mid+1;
        }else {r=mid-1;}
    }
    cout << max(le[ans1],chan[ans2]);
}

int main(){
	io();
    inp();
    solve();

	return 0;
}

Compilation message

lampice.cpp: In function 'void ioFile(std::string)':
lampice.cpp:40:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |     freopen((str+".in").c_str(),"r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
lampice.cpp:41:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |     freopen((str+".out").c_str(),"w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
lampice.cpp: In function 'void inp()':
lampice.cpp:53:25: warning: iteration 50006 invokes undefined behavior [-Waggressive-loop-optimizations]
   53 |     Foru(i,1,maxn) pw[i]=(1ll*pw[i-1]*base)%mod;
      |                    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
lampice.cpp:4:36: note: within this loop
    4 | #define Foru(i,a,b) for(int i=(a);i<=(b);++i)
      |                                    ^
lampice.cpp:53:5: note: in expansion of macro 'Foru'
   53 |     Foru(i,1,maxn) pw[i]=(1ll*pw[i-1]*base)%mod;
      |     ^~~~

Subtask #1
0 / 17.0

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

Subtask #2
0 / 25.0

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

Subtask #3
0 / 31.0

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

Subtask #4
0 / 37.0

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