oj.uz

Submission #359839

# Submission time Handle Problem Language Result Execution time Memory
359839 2021-01-27T08:52:05 Z juggernaut Simurgh (IOI17_simurgh) C++14
30 / 100
 392 ms 3692 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 1 ms 364 KB correct
2 Correct 1 ms 364 KB correct
3 Correct 1 ms 364 KB correct
4 Correct 1 ms 364 KB correct
5 Correct 1 ms 364 KB correct
6 Correct 1 ms 364 KB correct
7 Correct 1 ms 364 KB correct
8 Correct 1 ms 376 KB correct
9 Correct 1 ms 364 KB correct
10 Correct 1 ms 364 KB correct
11 Correct 1 ms 364 KB correct
12 Correct 1 ms 364 KB correct
13 Correct 1 ms 512 KB correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB correct
2 Correct 1 ms 364 KB correct
3 Correct 1 ms 364 KB correct
4 Correct 1 ms 364 KB correct
5 Correct 1 ms 364 KB correct
6 Correct 1 ms 364 KB correct
7 Correct 1 ms 364 KB correct
8 Correct 1 ms 376 KB correct
9 Correct 1 ms 364 KB correct
10 Correct 1 ms 364 KB correct
11 Correct 1 ms 364 KB correct
12 Correct 1 ms 364 KB correct
13 Correct 1 ms 512 KB correct
14 Correct 390 ms 492 KB correct
15 Correct 301 ms 492 KB correct
16 Correct 323 ms 492 KB correct
17 Correct 392 ms 512 KB correct
18 Correct 149 ms 492 KB correct
19 Correct 354 ms 492 KB correct
20 Correct 356 ms 512 KB correct
21 Correct 377 ms 492 KB correct
22 Correct 240 ms 492 KB correct
23 Correct 221 ms 492 KB correct
24 Correct 186 ms 492 KB correct
25 Correct 26 ms 364 KB correct
26 Correct 198 ms 364 KB correct
27 Correct 200 ms 364 KB correct
28 Correct 79 ms 492 KB correct
29 Correct 36 ms 364 KB correct
30 Correct 247 ms 492 KB correct
31 Correct 229 ms 492 KB correct
32 Correct 273 ms 492 KB correct
33 Correct 236 ms 364 KB correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB correct
2 Correct 1 ms 364 KB correct
3 Correct 1 ms 364 KB correct
4 Correct 1 ms 364 KB correct
5 Correct 1 ms 364 KB correct
6 Correct 1 ms 364 KB correct
7 Correct 1 ms 364 KB correct
8 Correct 1 ms 376 KB correct
9 Correct 1 ms 364 KB correct
10 Correct 1 ms 364 KB correct
11 Correct 1 ms 364 KB correct
12 Correct 1 ms 364 KB correct
13 Correct 1 ms 512 KB correct
14 Correct 390 ms 492 KB correct
15 Correct 301 ms 492 KB correct
16 Correct 323 ms 492 KB correct
17 Correct 392 ms 512 KB correct
18 Correct 149 ms 492 KB correct
19 Correct 354 ms 492 KB correct
20 Correct 356 ms 512 KB correct
21 Correct 377 ms 492 KB correct
22 Correct 240 ms 492 KB correct
23 Correct 221 ms 492 KB correct
24 Correct 186 ms 492 KB correct
25 Correct 26 ms 364 KB correct
26 Correct 198 ms 364 KB correct
27 Correct 200 ms 364 KB correct
28 Correct 79 ms 492 KB correct
29 Correct 36 ms 364 KB correct
30 Correct 247 ms 492 KB correct
31 Correct 229 ms 492 KB correct
32 Correct 273 ms 492 KB correct
33 Correct 236 ms 364 KB correct
34 Runtime error 8 ms 1644 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 364 KB correct
2 Correct 1 ms 364 KB correct
3 Runtime error 20 ms 3692 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 1 ms 364 KB correct
2 Correct 1 ms 364 KB correct
3 Correct 1 ms 364 KB correct
4 Correct 1 ms 364 KB correct
5 Correct 1 ms 364 KB correct
6 Correct 1 ms 364 KB correct
7 Correct 1 ms 364 KB correct
8 Correct 1 ms 376 KB correct
9 Correct 1 ms 364 KB correct
10 Correct 1 ms 364 KB correct
11 Correct 1 ms 364 KB correct
12 Correct 1 ms 364 KB correct
13 Correct 1 ms 512 KB correct
14 Correct 390 ms 492 KB correct
15 Correct 301 ms 492 KB correct
16 Correct 323 ms 492 KB correct
17 Correct 392 ms 512 KB correct
18 Correct 149 ms 492 KB correct
19 Correct 354 ms 492 KB correct
20 Correct 356 ms 512 KB correct
21 Correct 377 ms 492 KB correct
22 Correct 240 ms 492 KB correct
23 Correct 221 ms 492 KB correct
24 Correct 186 ms 492 KB correct
25 Correct 26 ms 364 KB correct
26 Correct 198 ms 364 KB correct
27 Correct 200 ms 364 KB correct
28 Correct 79 ms 492 KB correct
29 Correct 36 ms 364 KB correct
30 Correct 247 ms 492 KB correct
31 Correct 229 ms 492 KB correct
32 Correct 273 ms 492 KB correct
33 Correct 236 ms 364 KB correct
34 Runtime error 8 ms 1644 KB Execution killed with signal 11
35 Halted 0 ms 0 KB -