제출 #1125890

#제출 시각아이디문제언어결과실행 시간메모리
1125890TVSownLampice (COCI19_lampice)C++20
17 / 110
5109 ms353808 KiB
///*** Sown_Vipro ***/// /// ->TUYEN QUOC GIA<- /// #include<bits/stdc++.h> using namespace std; //#pragma GCC optimize ("O3") //#pragma GCC optimize ("unroll-loops") //#pragma GCC target("popcnt") #define F first #define S second #define pb push_back #define pi pair<int, int> #define pii pair<int, pair<int, int> > #define all(a) a.begin(), a.end() #define FOR(i, a, b) for(int i = a; i <= b; ++i) #define REP(i, a, b) for(int i = a; i >= b; --i) #define inp(name) if(fopen(name, "r")) freopen(name, "r", stdin); #define out(name) if(fopen(name, "w")) freopen(name, "w", stdout); const int N = 1e6 + 5, MAX = 1e6, oo = 1e9 + 5, MOD = 1e9 + 7, base = 311; int n, res, ans; int s[N], del[N], pw[N]; string str; vector<int> e[N]; map<int, int> f[N]; void count_child(int u, int p){ s[u] = 1; for(int v : e[u]){ if(v != p && !del[v]){ count_child(v, u); s[u] += s[v]; } } } int find_centroid(int u, int p, int n){ for(int v : e[u]){ if(v != p && !del[v] && s[v] > n) return find_centroid(v, u, n); } return u; } void dfs(int u, int p, int k, int h, int up, int down, int type){ if(k < h) return; down = (1ll * down * base + str[u]) % MOD; up = (1ll * str[u] * pw[h - 1] + up) % MOD; int x = (1ll * up * pw[k - h] - down + MOD) % MOD; if(type <= 1) f[h - 1][x] = type; else res = max(res, k * f[k - h][x]); for(int v : e[u]){ if(v != p && !del[v]){ dfs(v, u, k, h + 1, up, down, type); } } } void build(int u, int k){ count_child(u, 0); int cen = find_centroid(u, 0, s[u] / 2); del[cen] = 1; int x = (-str[cen] + MOD) % MOD; f[0][x] = 1; for(int v : e[cen]){ if(del[v]) continue; dfs(v, cen, k, 2, 0, str[cen], 2); dfs(v, cen, k, 2, 0, str[cen], 1); } f[0][x] = 0; for(int v : e[cen]){ if(del[v]) continue; dfs(v, cen, k, 2, 0, str[cen], 0); } if(res == k) return; for(int v : e[cen]){ if(!del[v]) build(v, k); } } void solve(){ cin >> n; cin >> str; str = "#" + str; FOR(i, 2, n){ int u, v; cin >> u >> v; e[u].pb(v); e[v].pb(u); } pw[0] = 1; FOR(i, 1, n) pw[i] = (1ll * pw[i - 1] * base) % MOD; int l = 1, r = n; ans = 1; while(l <= r){ int mid = (l + r) / 2; FOR(u, 1, n) del[u] = 0; res = 1; build(1, mid * 2); if(res == mid * 2){ l = mid + 1; ans = max(ans, res); }else r = mid - 1; } l = 1; r = n; while(l <= r){ int mid = (l + r) / 2; FOR(u, 1, n) del[u] = 0; res = 1; build(1, mid * 2 + 1); if(res == mid * 2 + 1){ l = mid + 1; ans = max(ans, res); }else r = mid - 1; } cout << ans; } signed main(){ ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); inp("in.txt"); // out("out.txt"); int t = 1; // cin >> t; while(t--){ solve(); } }

컴파일 시 표준 에러 (stderr) 메시지

lampice.cpp: In function 'int main()':
lampice.cpp:17:47: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 | #define inp(name) if(fopen(name, "r")) freopen(name, "r", stdin);
      |                                        ~~~~~~~^~~~~~~~~~~~~~~~~~
lampice.cpp:127:5: note: in expansion of macro 'inp'
  127 |     inp("in.txt");
      |     ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...