oj.uz

Submission #466344

# Submission time Handle Problem Language Result Execution time Memory
466344 2021-08-18T19:24:38 Z MohamedAliSaidane Islands (IOI08_islands) C++14
6 / 100
 2000 ms 131072 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;

typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<ld,ld> pld;

typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pii> vpi;

#define pb push_back
#define popb pop_back
#define all(v) (v).begin(),(v).end()
#define ff first
#define ss second

const int MOD = 1e9 + 7;
const ll INF = 1e18;
const int MAX_N = 4005;
int n;
ll adj[MAX_N][MAX_N];
bool visited[MAX_N];

ll dfs(int u)
{
    visited[u] = true;
    ll maxt = 0;
    for(int i = 1; i <= n; i ++)
    {
        if(visited[i])
            continue;
        maxt = max(maxt,dfs(i)+adj[u][i]);
    }
    visited[u] = false;
    return maxt;

}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    memset(adj,0,sizeof(adj));
    cin >> n;
    for(int i = 1; i <=n; i ++)
    {
        ll u, dist;
        cin >> u >> dist;
        adj[i][u] = adj[u][i] = max(adj[i][u],dist);
    }
    ll ans = 0;
    for(int i = 1; i <=n; i ++)
    {
        ans=max(ans,dfs(i));
    }
    cout << ans;
}
/*
Sample test case:
7
3 8
7 2
4 2
1 4
1 9
3 4
2 3
*/

Subtask #1
6.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 125768 KB Output is correct
2 Execution timed out 2093 ms 125764 KB Time limit exceeded
3 Execution timed out 2086 ms 125764 KB Time limit exceeded
4 Correct 55 ms 125764 KB Output is correct
5 Execution timed out 2082 ms 125756 KB Time limit exceeded
6 Execution timed out 2074 ms 125832 KB Time limit exceeded
7 Execution timed out 2079 ms 125764 KB Time limit exceeded
8 Execution timed out 2084 ms 125824 KB Time limit exceeded
9 Execution timed out 2078 ms 125808 KB Time limit exceeded
10 Execution timed out 2075 ms 125772 KB Time limit exceeded
11 Execution timed out 2074 ms 125768 KB Time limit exceeded

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2099 ms 125852 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 4.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2085 ms 125892 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 204 ms 131072 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 203 ms 131072 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 218 ms 131072 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 217 ms 131072 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 208 ms 131072 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 198 ms 131072 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -