oj.uz

Submission #423216

# Submission time Handle Problem Language Result Execution time Memory
423216 2021-06-10T20:07:40 Z Monchito Split the Attractions (IOI19_split) C++14
18 / 100
 129 ms 18076 KB 
#include "split.h"
#include <algorithm>
using namespace std;
using vi = vector<int>;

const int MAXN = 1e5;
vi G[MAXN], CC[MAXN];
bool vis[MAXN];

void DFS(int current_node, int current_CC){
    vis[current_node] = true;
    CC[current_CC].push_back(current_node);   

    for(int v : G[current_node]){
        if(!vis[v]) DFS(v, current_CC);
    }
}

vector<int> find_split(int n, int a, int b, int c, vi p, vi q){
	vi res(n, 0);

    for(int i=0; i<(int)p.size(); i++){
        G[p[i]].push_back(q[i]);
        G[q[i]].push_back(p[i]);
    }

    int current_CC = 0;

    for(int i=0; i<n; i++){
        if(!vis[i]) { DFS(i, current_CC); current_CC++; }
    }

    pair<int,int> CC_info[current_CC], values[3] = { {a, 1}, {b, 2}, {c, 3} };
    for(int i=0; i<current_CC; i++) { CC_info[i].first = CC[i].size(); CC_info[i].second = i; }

    sort(CC_info, CC_info + current_CC);
    sort(values, values+3);

    for(int i=0; i<2; i++){
        bool can = false;

        for(int j=0; j<current_CC; j++){
            if(CC_info[j].first >= values[i].first){
                for(int z = CC_info[j].first-1; z >= CC_info[j].first - values[i].first; z--)
                    res[CC[CC_info[j].second][z]] = values[i].second;

                CC_info[j].first -= values[i].first; 
                can = true;
                break;
            }
        }

        if(!can) { res = vi(n, 0); return res; }
    }

    for(int i=0; i<current_CC; i++){
        for(int j=CC_info[i].first-1; j >= 0; j--)
            res[CC[CC_info[i].second][j]] = values[2].second;
    }

	return res;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB ok, correct split
2 Correct 3 ms 4976 KB ok, correct split
3 Correct 3 ms 4940 KB ok, correct split
4 Correct 3 ms 4940 KB ok, correct split
5 Correct 3 ms 4968 KB ok, correct split
6 Correct 3 ms 4940 KB ok, correct split
7 Correct 78 ms 17660 KB ok, correct split
8 Correct 76 ms 15940 KB ok, correct split
9 Correct 86 ms 15348 KB ok, correct split
10 Correct 76 ms 18040 KB ok, correct split
11 Correct 100 ms 18076 KB ok, correct split

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB ok, correct split
2 Correct 4 ms 4980 KB ok, correct split
3 Correct 3 ms 4976 KB ok, correct split
4 Correct 92 ms 16500 KB ok, correct split
5 Correct 71 ms 12016 KB ok, correct split
6 Correct 78 ms 18032 KB ok, correct split
7 Correct 87 ms 15864 KB ok, correct split
8 Correct 129 ms 15288 KB ok, correct split
9 Correct 71 ms 11976 KB ok, correct split
10 Correct 57 ms 12020 KB ok, correct split
11 Correct 56 ms 11964 KB ok, correct split
12 Correct 56 ms 12400 KB ok, correct split

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB ok, correct split
2 Incorrect 71 ms 12000 KB 2 components are not connected
3 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 4940 KB 2 components are not connected
2 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB ok, correct split
2 Correct 3 ms 4976 KB ok, correct split
3 Correct 3 ms 4940 KB ok, correct split
4 Correct 3 ms 4940 KB ok, correct split
5 Correct 3 ms 4968 KB ok, correct split
6 Correct 3 ms 4940 KB ok, correct split
7 Correct 78 ms 17660 KB ok, correct split
8 Correct 76 ms 15940 KB ok, correct split
9 Correct 86 ms 15348 KB ok, correct split
10 Correct 76 ms 18040 KB ok, correct split
11 Correct 100 ms 18076 KB ok, correct split
12 Correct 3 ms 4940 KB ok, correct split
13 Correct 4 ms 4980 KB ok, correct split
14 Correct 3 ms 4976 KB ok, correct split
15 Correct 92 ms 16500 KB ok, correct split
16 Correct 71 ms 12016 KB ok, correct split
17 Correct 78 ms 18032 KB ok, correct split
18 Correct 87 ms 15864 KB ok, correct split
19 Correct 129 ms 15288 KB ok, correct split
20 Correct 71 ms 11976 KB ok, correct split
21 Correct 57 ms 12020 KB ok, correct split
22 Correct 56 ms 11964 KB ok, correct split
23 Correct 56 ms 12400 KB ok, correct split
24 Correct 3 ms 4940 KB ok, correct split
25 Incorrect 71 ms 12000 KB 2 components are not connected
26 Halted 0 ms 0 KB -