oj.uz

Submission #960955

# Submission time Handle Problem Language Result Execution time Memory
960955 2024-04-11T09:49:42 Z Trisanu_Das Simurgh (IOI17_simurgh) C++17
30 / 100
 252 ms 3676 KB 
#include"simurgh.h"
#ifndef EVAL
#include"grader.cpp"
#endif
#include<bits/stdc++.h>
using namespace std;
int g[55][55],good[3025],n,used[55];
vector<int>cur;
void init(int v){
    used[v]=1;
    for(int i=0;i<n;i++)
        if(!used[i]&&g[v][i]>=0){
            cur.push_back(g[v][i]);
            init(i);
        }
}
void dfs(int v){
    used[v]=1;
    for(int i=0;i<n;i++)
        if(used[i]==0&&g[v][i]>=0&&good[g[v][i]]==1)dfs(i);
}
bool check(){
    memset(used,0,sizeof(used));
    memset(good,0,sizeof(good));
    for(int i:cur)good[i]=1;
    dfs(0);
    for(int i=0;i<n;i++)
        if(used[i]==0)return 0;
    return 1;
}
vector<int>find_roads(int N,vector<int>u,vector<int>v){
    n=N;
    int m=u.size();
    memset(g,-1,sizeof(g));
    for(int i=0;i<m;i++)g[u[i]][v[i]]=g[v[i]][u[i]]=i;
    init(0);
    while(true){
        int now=count_common_roads(cur);
        if(now==n-1)return cur;
        for(int i=0;i<n-1;i++){
            for(int j=0;j<m;j++){
                if(cur[i]!=j){
                    int old=cur[i];
                    cur[i]=j;
                    if(check()){
                        int temp=count_common_roads(cur);
                        if(temp>now)now=temp;
                        else cur[i]=old;
                    }else cur[i]=old;
                }
            }
        }
    }
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB correct
2 Correct 0 ms 348 KB correct
3 Correct 1 ms 348 KB correct
4 Correct 0 ms 348 KB correct
5 Correct 1 ms 348 KB correct
6 Correct 1 ms 348 KB correct
7 Correct 1 ms 348 KB correct
8 Correct 0 ms 348 KB correct
9 Correct 0 ms 436 KB correct
10 Correct 1 ms 348 KB correct
11 Correct 0 ms 600 KB correct
12 Correct 1 ms 600 KB correct
13 Correct 1 ms 436 KB correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB correct
2 Correct 0 ms 348 KB correct
3 Correct 1 ms 348 KB correct
4 Correct 0 ms 348 KB correct
5 Correct 1 ms 348 KB correct
6 Correct 1 ms 348 KB correct
7 Correct 1 ms 348 KB correct
8 Correct 0 ms 348 KB correct
9 Correct 0 ms 436 KB correct
10 Correct 1 ms 348 KB correct
11 Correct 0 ms 600 KB correct
12 Correct 1 ms 600 KB correct
13 Correct 1 ms 436 KB correct
14 Correct 252 ms 464 KB correct
15 Correct 186 ms 460 KB correct
16 Correct 199 ms 460 KB correct
17 Correct 239 ms 456 KB correct
18 Correct 91 ms 448 KB correct
19 Correct 206 ms 348 KB correct
20 Correct 213 ms 452 KB correct
21 Correct 221 ms 344 KB correct
22 Correct 149 ms 348 KB correct
23 Correct 122 ms 452 KB correct
24 Correct 108 ms 448 KB correct
25 Correct 12 ms 460 KB correct
26 Correct 123 ms 452 KB correct
27 Correct 129 ms 448 KB correct
28 Correct 42 ms 348 KB correct
29 Correct 19 ms 604 KB correct
30 Correct 156 ms 444 KB correct
31 Correct 139 ms 448 KB correct
32 Correct 164 ms 452 KB correct
33 Correct 146 ms 448 KB correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB correct
2 Correct 0 ms 348 KB correct
3 Correct 1 ms 348 KB correct
4 Correct 0 ms 348 KB correct
5 Correct 1 ms 348 KB correct
6 Correct 1 ms 348 KB correct
7 Correct 1 ms 348 KB correct
8 Correct 0 ms 348 KB correct
9 Correct 0 ms 436 KB correct
10 Correct 1 ms 348 KB correct
11 Correct 0 ms 600 KB correct
12 Correct 1 ms 600 KB correct
13 Correct 1 ms 436 KB correct
14 Correct 252 ms 464 KB correct
15 Correct 186 ms 460 KB correct
16 Correct 199 ms 460 KB correct
17 Correct 239 ms 456 KB correct
18 Correct 91 ms 448 KB correct
19 Correct 206 ms 348 KB correct
20 Correct 213 ms 452 KB correct
21 Correct 221 ms 344 KB correct
22 Correct 149 ms 348 KB correct
23 Correct 122 ms 452 KB correct
24 Correct 108 ms 448 KB correct
25 Correct 12 ms 460 KB correct
26 Correct 123 ms 452 KB correct
27 Correct 129 ms 448 KB correct
28 Correct 42 ms 348 KB correct
29 Correct 19 ms 604 KB correct
30 Correct 156 ms 444 KB correct
31 Correct 139 ms 448 KB correct
32 Correct 164 ms 452 KB correct
33 Correct 146 ms 448 KB correct
34 Runtime error 5 ms 1476 KB Execution killed with signal 11
35 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB correct
2 Correct 1 ms 348 KB correct
3 Runtime error 18 ms 3676 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB correct
2 Correct 0 ms 348 KB correct
3 Correct 1 ms 348 KB correct
4 Correct 0 ms 348 KB correct
5 Correct 1 ms 348 KB correct
6 Correct 1 ms 348 KB correct
7 Correct 1 ms 348 KB correct
8 Correct 0 ms 348 KB correct
9 Correct 0 ms 436 KB correct
10 Correct 1 ms 348 KB correct
11 Correct 0 ms 600 KB correct
12 Correct 1 ms 600 KB correct
13 Correct 1 ms 436 KB correct
14 Correct 252 ms 464 KB correct
15 Correct 186 ms 460 KB correct
16 Correct 199 ms 460 KB correct
17 Correct 239 ms 456 KB correct
18 Correct 91 ms 448 KB correct
19 Correct 206 ms 348 KB correct
20 Correct 213 ms 452 KB correct
21 Correct 221 ms 344 KB correct
22 Correct 149 ms 348 KB correct
23 Correct 122 ms 452 KB correct
24 Correct 108 ms 448 KB correct
25 Correct 12 ms 460 KB correct
26 Correct 123 ms 452 KB correct
27 Correct 129 ms 448 KB correct
28 Correct 42 ms 348 KB correct
29 Correct 19 ms 604 KB correct
30 Correct 156 ms 444 KB correct
31 Correct 139 ms 448 KB correct
32 Correct 164 ms 452 KB correct
33 Correct 146 ms 448 KB correct
34 Runtime error 5 ms 1476 KB Execution killed with signal 11
35 Halted 0 ms 0 KB -