#include <bits/stdc++.h>
using namespace std;
#define fileIO(name) if(fopen(name".inp", "r")) {freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout);}
#define SPEED {ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0);}
template<class T1, class T2> bool minimize(T1 &a, T2 b){return a > b ? a = b, true : false;}
template<class T1, class T2> bool maximize(T1 &a, T2 b){return a < b ? a = b, true : false;}
const int N = 505;
int n, type, res, res_vtx, nxt[N], prv[N];
int adj[N][N], dp[N][N][2], f[N][N][2];
int main(){
SPEED; fileIO("text");
cin >> n >> type;
for(int u = 1, v; u <= n; ++u){
cin >> v;
while(v > 0){
adj[u][v] = 1;
cin >> v;
}
nxt[u] = u + 1; prv[u] = u - 1;
}
nxt[n] = 1; prv[1] = n;
for(int len = 2; len <= n; ++len){
for(int i = 1; i <= n; ++i){
int j = i + len - 1;
if(j > n) j -= n;
//compute dp[i][j][0]
if(adj[i][j]) dp[i][j][0] = 1 + dp[j][nxt[i]][1];
for(int k = i; k != j; k = nxt[k]) if(adj[i][k]){
maximize(dp[i][j][0], max(dp[k][j][0], dp[k][nxt[i]][1]) + 1);
}
//compute dp[j][i][1]
if(adj[j][i]) dp[j][i][1] = 1 + dp[i][prv[j]][0];
for(int k = j; k != i; k = prv[k]) if(adj[j][k]){
maximize(dp[j][i][1], max(dp[k][prv[j]][0], dp[k][i][1]) + 1);
}
if(maximize(res, dp[i][j][0])) res_vtx = i;
if(maximize(res, dp[j][i][1])) res_vtx = j;
}
}
if(type){
for(int len = 2; len <= n; ++len){
for(int i = 1; i <= n; ++i){
int j = i + len - 1;
if(j > n) j -= n;
//compute f[i][j][0];
if(adj[i][j]) f[i][j][0] = 1;
for(int k = i; k != j; k = nxt[k]) if(adj[i][k] && f[k][j][0]){
maximize(f[i][j][0], f[k][j][0] + 1);
}
//compute f[j][i][1]
if(adj[j][i]) f[j][i][1] = 1;
for(int k = j; k != i; k = prv[k]) if(adj[j][k] && f[k][i][1]){
maximize(f[j][i][1], f[k][i][1] + 1);
}
}
}
for(int a = 1; a <= n; ++a){
for(int b = nxt[a]; b != a; b = nxt[b]){
for(int c = nxt[a], ma = -1; c != b; c = nxt[c]){
if(adj[a][c] && ma >= 0 && f[c][b][0]){
if(maximize(res, f[c][b][0] + 2 + ma)) res_vtx = a;
}
if(adj[b][c]) maximize(ma, dp[c][nxt[a]][1]);
}
for(int c = prv[a], ma = -1; c != b; c = prv[c]){
if(adj[a][c] && ma >= 0 && f[c][b][1]){
if(maximize(res, f[c][b][1] + 2 + ma)) res_vtx = a;
}
if(adj[b][c]) maximize(ma, dp[c][prv[a]][0]);
}
}
}
for(int c = 1; c <= n; ++c){
for(int d = nxt[c]; d != c; d = nxt[d]){
for(int a = nxt[d], ma = -1; a != c; a = nxt[a]){
if(adj[a][d] && ma >= 0){
if(maximize(res, dp[c][prv[d]][0] + 2 + ma)) res_vtx = a;
}
if(adj[a][c] && f[d][a][0]) maximize(ma, f[d][a][0]);
}
for(int a = prv[d], ma = -1; a != c; a = prv[a]){
if(adj[a][d] && ma >= 0){
if(maximize(res, dp[c][nxt[d]][1] + 2 + ma)) res_vtx = a;
}
if(adj[a][c] && f[d][a][1]) maximize(ma, f[d][a][1]);
}
}
}
}
cout << res << '\n' << res_vtx;
return 0;
}
Compilation message
race.cpp: In function 'int main()':
race.cpp:4:57: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
4 | #define fileIO(name) if(fopen(name".inp", "r")) {freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout);}
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
race.cpp:13:12: note: in expansion of macro 'fileIO'
13 | SPEED; fileIO("text");
| ^~~~~~
race.cpp:4:90: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
4 | #define fileIO(name) if(fopen(name".inp", "r")) {freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout);}
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
race.cpp:13:12: note: in expansion of macro 'fileIO'
13 | SPEED; fileIO("text");
| ^~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
468 KB |
Output is correct |
| 3 |
Correct |
1 ms |
596 KB |
Output is correct |
| 4 |
Correct |
2 ms |
724 KB |
Output is correct |
| 5 |
Correct |
1 ms |
596 KB |
Output is correct |
| 6 |
Correct |
5 ms |
852 KB |
Output is correct |
| 7 |
Correct |
3 ms |
724 KB |
Output is correct |
| 8 |
Correct |
9 ms |
1108 KB |
Output is correct |
| 9 |
Correct |
5 ms |
876 KB |
Output is correct |
| 10 |
Correct |
4 ms |
852 KB |
Output is correct |
| 11 |
Correct |
7 ms |
932 KB |
Output is correct |
| 12 |
Correct |
141 ms |
2296 KB |
Output is correct |
| 13 |
Correct |
362 ms |
3280 KB |
Output is correct |
| 14 |
Correct |
168 ms |
2692 KB |
Output is correct |
| 15 |
Correct |
1830 ms |
5256 KB |
Output is correct |
| 16 |
Correct |
2083 ms |
5260 KB |
Output is correct |
| 17 |
Correct |
1848 ms |
5256 KB |
Output is correct |
| 18 |
Correct |
294 ms |
3284 KB |
Output is correct |
| 19 |
Correct |
2330 ms |
5208 KB |
Output is correct |
| 20 |
Correct |
2298 ms |
5264 KB |
Output is correct |
