제출 #1206577

#제출 시각아이디문제언어결과실행 시간메모리
1206577hyakupClosing Time (IOI23_closing)C++20
9 / 100
1096 ms30248 KiB
#include "closing.h" #include <bits/stdc++.h> using namespace std; const int maxn = 2e5; using ll = long long; using pll = pair<ll, int>; const ll inf = 1e18; vector<vector<pair<int, int>>> adj; vector<vector<ll>> dist; vector<vector<int>> pai; void init( int n ){ adj.clear(); adj.resize(n); dist.clear(); dist.resize( 2, vector<ll>(n)); pai.clear(); pai.resize( 2, vector<int>(n)); } void dfs( int cur, int last, int t ){ pai[t][cur] = last; for( auto [viz, d] : adj[cur] ) if( viz != last ){ dist[t][viz] = dist[t][cur] + d; dfs( viz, cur, t ); } } int max_score(int n, int x, int y, long long val, vector<int> a, vector<int> b, vector<int> c ) { init(n); int m = a.size(); for( int i = 0; i < m; i++ ){ adj[a[i]].push_back({ b[i], c[i] }); adj[b[i]].push_back({ a[i], c[i] }); } dfs( x, x, 0 ); dfs( y, y, 1 ); vector<ll> s1(n + 1), s2(n + 1); for( int i = 0; i < n; i++ ){ s1[i + 1] = min( dist[0][i], dist[1][i] ) + s1[i]; s2[i + 1] = abs( dist[0][i] - dist[1][i] ) + s2[i]; } int resp = 0; for( int i = 0; i <= x; i++ ){ for( int j = y; j < n; j++ ){ for( int k = x; k < n; k++ ){ for( int l = 0; l <= y; l++ ){ ll sum; if( k < l ){ sum = s1[k + 1] - s1[i] + s1[j + 1] - s1[l]; } else{ sum = s1[max(j, k) + 1] - s1[min(i, l)] + s2[min(j, k) + 1] - s2[max(i, l)]; } if( sum <= val ){ resp = max( resp, k - i + 1 + j - l + 1 ); } } } } } return resp; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...