Submission

Score: 100

User: dddrrrr

Problemset: forex

Language: cpp

Time: 0.625 second

Submitted On: 2026-03-13 08:37:01

#include <bits/stdc++.h>
#define int long long
const int MOD = 1e7 + 9;
using namespace std;

int n;
vector <int> ans;
vector <vector <double>> adj(39 ,vector <double>(39));
vector <vector <double>> best(39 ,vector <double>(39 ,0));

void dfs(int node ,vector <bool>& in_stack ,vector <int>& dist ,vector <double>& money ,int src){
	if(!ans.empty() && dist[node] >= ans[0])return ;
	if(dist[node] >= n)return ;
	
	if(money[node] < best[node][dist[node]])return ;
	best[node][dist[node]] = money[node];
	
	
	
	in_stack[node] = true; 
	for(int v=0 ;v<n ;v++){
		if(v == node)continue;

		double w=adj[node][v];
		if(v == src && dist[node] > 0){
			//cycle found
			if(money[node] * w > 1.00000001){
				ans.emplace_back(dist[node] + 1);
			}
		}
		if(!in_stack[v]){
			int a = dist[v];
			double b = money[v];
			
			dist[v] = dist[node] + 1;
			money[v] = money[node] * w;
			dfs(v ,in_stack ,dist ,money ,src);
			
			dist[v] = a;
			money[v] = b;
		 }
	}
	in_stack[node] = false;
	return ;
}

int32_t main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	cin >> n;
	
	for(int i=0 ;i<n ;i++){
		for(int j=0 ;j<n ;j++){
			cin >> adj[i][j];
		}
	}	
	
	vector <pair <int ,int>> res;
	for(int i=0 ;i<n ;i++){
		vector <bool> in_stack(n ,false);
		vector <int> dist(n ,0);
		vector <double> money(n ,1);
		ans.clear();

		dfs(i ,in_stack ,dist ,money ,i);
		if(!ans.empty()){
			for(auto it : ans)res.emplace_back(i+1 ,it);
		}
	}
	
	sort(res.begin() ,res.end() ,[](const pair <int ,int>& a ,const pair <int ,int>& b){
		if(a.second != b.second)return a.second < b.second;
		return a.first < b.first;
	});	
	
	if(!res.empty())cout << res[0].first << ' ' << res[0].second;
	else cout << -1;
	
	return 0;
}