/*
ID: swagchicken1
PROG:
LANG: C++11
*/
#include <iostream>
#include <tuple>
#include <cmath>
#include <string>
#include <cstring>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <algorithm>
#include <vector>
#include <fstream>
#include <iomanip>
#include <ctime>
#include <cctype>
#include <climits>
#include <chrono>
#include <numeric>
#include <functional>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector< vector <int> > vvi;
typedef pair<int, int> pii;
typedef pair < pair < int, int >, int > piii;
typedef pair < pair <int, int > , pair <int, int> > piiii;
typedef pair<ll, ll> pll;
typedef vector<bool> vb;
typedef vector<char> vc;
typedef vector<string> vs;
#define FOR(i,a,b) for(int i = a; i < b; i ++)
#define RFOR(i,a,b) for(int i = a-1; i >= b; i --)
#define all(a) a.begin(), a.end()
#define endl '\n';
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define ff first
#define ss second
template <typename T>
void pr(vector<T> &v) {
FOR(i, 0, sz(v)) cout << v[i] << " ";
cout << endl;
}
template <typename T>
void pr(vector<vector<T> > &v) {
FOR(i, 0, sz(v)) { pr(v[i]); }
}
template <typename T>
void re(T &x) {
cin >> x;
}
template <typename T>
void re(vector<T> &a) {
FOR(i, 0, sz(a)) re(a[i]);
}
template <class Arg, class... Args>
void re(Arg &first, Args &... rest) {
re(first);
re(rest...);
}
template <typename T>
void pr(T x) {
cout << x << endl;
}
template <class Arg, class... Args>
void pr(const Arg &first, const Args &... rest) {
cout << first << " ";
pr(rest...);
cout << endl;
}
void ps() { cout << endl; }
template<class T, class... Ts>
void ps(const T& t, const Ts&... ts) {
cout << t; if (sizeof...(ts)) cout << " "; ps(ts...);
}
const ll MOD = 1000000007;
#define inf 1e18;
#define INF INT_MAX
//#define DEBUG
long double PI = 4*atan(1);
long double eps = 1e-9;
int cw[510][510];
int cc[510][510];
vvi adj(510);
vvi radj(510);
int edge[510][510] = {};
int main() {
//auto start = chrono::high_resolution_clock::now();
ios_base::sync_with_stdio(0);cin.tie(0);
//ofstream cout("output.txt");
//ifstream cin("input.txt");
#ifdef DEBUG
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
// freopen("pieaters.in", "r", stdin);
// freopen("pieaters.out", "w", stdout);
#endif
int n, K; cin >> n >> K;
FOR(i,0,n) {
int v = -1;
while(cin >> v) {
v--;
if(v == -1) break;
// cout << i << " " << v << endl;
adj[i].pb(v);
radj[v].pb(i);
edge[i][v] = 1;
}
}
FOR(d,2,n+1) {
FOR(i,0,n) {
int jcw = (i + d)%n;
int k = i + 1; if(k == n) k = 0;
// go clockwise;
while(k != jcw) {
if(edge[i][k]) {
cw[i][jcw] = max(cw[i][jcw], 1 + max(cc[k][i], cw[k][jcw]));
}
k++;
if(k == n) k = 0;
}
int jcc = (i + n - d)%n;
k = i - 1; if(k == -1) k = n-1;
// go clockwise from ccw
while(k != jcc) {
if(edge[i][k]) {
cc[i][jcc] = max(cc[i][jcc], 1 + max(cw[k][i], cc[k][jcc]));
}
k--;
if(k == -1) k = n-1;
}
}
}
int ans = 0;
int idx = 0;
// FOR(i,0,n) {FOR(j,0,n) {cout << cw[i][j] << " ";} cout << endl;}
// cout << endl;
// FOR(i,0,n) {FOR(j,0,n) {cout << cc[i][j] << " ";} cout << endl;}
FOR(i,0,n) {
FOR(j,0,n) {
ans = max(ans, cc[i][j]);
if(cc[i][j] == ans) {
idx = i;
// cout << "COUNTERCLOCKWISE " << i << " to " << j << " len " << ans << endl;
}
ans = max(ans, cw[i][j]);
if(cw[i][j] == ans) {
idx = i;
// cout << "CLOCKWISE " << i << " to " << j << " len " << ans << endl;
}
}
}
if(K == 0) {
cout << ans << endl;
cout << idx + 1 << endl;
return 0;
}
FOR(i,0,n) {
//clockwise
int j = i + 1;
if(j == n) j = 0;
vi dist(510, -1e9);
vi vis(510);
dist[i] = 0;
vis[i] = 1;
vector<pii> cross;
while(j != i) {
int prev = j-1;
if(prev == -1) prev = n-1;
for(int v : radj[j]) {
if(vis[v]) {
dist[j] = max(dist[j], dist[v] + 1);
}
}
if(prev != i && dist[prev] > 0) {
for(int v : adj[prev]) {
cross.pb({v, prev});
}
}
vis[j] = 1;
if(edge[j][i]) {
while(!cross.empty()) {
pii x = cross.back();
if(!vis[x.ff]) {
int temp = 2 + dist[x.ss] + max(cw[x.ff][i], cc[x.ff][j]);
if(temp > ans) {
cout << "a" << temp << " " << j << endl;
// cout << temp << " " << j << " " << i << " " << x.ss << " " << x.ff << endl;
ans = temp;
idx = j;
}
}
cross.pop_back();
}
}
j++;
if(j == n) j -= n;
}
j = i - 1;
if(j == -1) j = n-1;
dist.assign(510, -1e9);
vis.assign(510, 0);
dist[i] = 0;
vis[i] = 1;
cross.clear();
while(j != i) {
int prev = j+1;
if(prev == n) prev = 0;
for(int v : radj[j]) {
if(vis[v]) {
dist[j] = max(dist[j], dist[v] + 1);
}
}
if(prev != i && dist[prev] > 0) {
for(int v : adj[prev]) {
cross.pb({v, prev});
}
}
vis[j] = 1;
if(edge[j][i]) {
while(!cross.empty()) {
pii x = cross.back();
if(!vis[x.ff]) {
int temp = 2 + dist[x.ss] + max(cw[x.ff][j], cc[x.ff][i]);
if(temp > ans) {
ans = temp;
idx = j;
}
}
cross.pop_back();
}
}
j--;
if(j == -1) j = n-1;
}
}
cout << ans << endl;
cout << idx + 1 << endl;
//auto stop = chrono::high_resolution_clock::now();
//auto duration = chrono::duration_cast<chrono::microseconds>(stop - start);
//cout << duration.count() << endl;
//cin.close();
//cout.close();
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
468 KB |
Expected integer, but "a13" found |
| 3 |
Incorrect |
1 ms |
468 KB |
Expected integer, but "a12" found |
| 4 |
Correct |
1 ms |
596 KB |
Output is correct |
| 5 |
Correct |
1 ms |
596 KB |
Output is correct |
| 6 |
Correct |
3 ms |
700 KB |
Output is correct |
| 7 |
Correct |
3 ms |
724 KB |
Output is correct |
| 8 |
Incorrect |
4 ms |
852 KB |
Expected integer, but "a38" found |
| 9 |
Correct |
5 ms |
852 KB |
Output is correct |
| 10 |
Correct |
5 ms |
980 KB |
Output is correct |
| 11 |
Correct |
6 ms |
1016 KB |
Output is correct |
| 12 |
Correct |
58 ms |
1636 KB |
Output is correct |
| 13 |
Incorrect |
116 ms |
2296 KB |
Expected integer, but "a96" found |
| 14 |
Correct |
130 ms |
2876 KB |
Output is correct |
| 15 |
Incorrect |
661 ms |
3780 KB |
Expected integer, but "a194" found |
| 16 |
Correct |
843 ms |
4012 KB |
Output is correct |
| 17 |
Incorrect |
680 ms |
3784 KB |
Expected integer, but "a191" found |
| 18 |
Correct |
217 ms |
3492 KB |
Output is correct |
| 19 |
Correct |
999 ms |
4020 KB |
Output is correct |
| 20 |
Incorrect |
995 ms |
4024 KB |
Expected integer, but "a263" found |
