Submission

Score: 0

User: dddrrrr

Problemset: forex

Language: cpp

Time: 0.002 second

Submitted On: 2026-03-12 23:20:49

#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));
void dfs(int node ,vector <bool>& vs ,vector <bool>& in_stack ,vector <int>& dist ,vector <double>& money ,int src){
	in_stack[node] = true; 
	for(int i=0 ;i<n ;i++){
		if(!ans.empty())return ;
		if(i == node)continue;
		
		int v=i ;
		double w=adj[node][i];
		if(!vs[v]){
			dist[v] = dist[node] + 1;
			money[v] = money[node] * w;
			vs[v] = true;
			dfs(v ,vs ,in_stack ,dist ,money ,src);
		}
		else if(in_stack[v] && v == src){
			//cycle found
			money[v] = money[node]*w;
			dist[v] = dist[node]+1;
			if(money[v] > 1){
				ans.emplace_back(dist[v]);
			}
		}
	}
	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> vs(n ,false) ,in_stack(n ,false);
		vector <int> dist(n ,0);
		vector <double> money(n ,1);
		ans.clear();
		vs[i] = true;
		dfs(i ,vs ,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;
	});	
	
	cout << res[0].first << ' ' << res[0].second;
	
	return 0;
}