oj.uz

Submission #233210

# Submission time Handle Problem Language Result Execution time Memory
233210 2020-05-19T22:43:46 Z UserIsUndefined Split the Attractions (IOI19_split) C++14
18 / 100
 153 ms 22612 KB 
#include <bits/stdc++.h>
#include "split.h"

using namespace std;


vector<int> adj[100005];
int children[100005];
bool visited[100005];
vector<int> adj2[100005];
int ans[100005];
int mark;
int sz;
bool ok;
int doo;
int nn;

void dfs(int v){
    visited[v] = true;

    for (int i : adj[v]){
        if (visited[i] == false){
            dfs(i);
            children[v]+= children[i];
            adj2[v].push_back(i);
        }
    }

    children[v]++;

    if ((children[v] >= sz)&&(ok == false)&&(nn - children[v] > sz)){
        doo = v;
        ok = true;
    }

}



void dfs2(int v){
    visited[v] = true;
    ans[v] = mark;

    for (int i : adj2[v]){
        if ((visited[i] == false)&&(sz)){
            sz--;
            dfs2(i);
        }
    }

}


vector<int> comp;


void dfs3(int v){
    visited[v] = true;
    comp.push_back(v);

    for (int i : adj[v]){
        if (visited[i] == false){
            dfs3(i);
        }
    }


}








vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
	vector<int> res(n, 0);
    vector<pair<int,int>> abc;
    nn = n;
    abc.push_back({a, 1});
    abc.push_back({b, 2});
    abc.push_back({c, 3});

    sort(abc.begin() , abc.end());


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


    doo = -1;
    ok = false;
    mark = abc[0].second;
    sz = abc[0].first;


    dfs(0);

    if (doo == -1){
        vector<int> emptyy(n,0);
        return emptyy;
    }

    memset(visited , false , sizeof visited);
    sz--;
    dfs2(doo);

//    cout << "this is res :  " ;
//    for (int i = 0 ; i < 10 ; i++){
//        cout << ans[i] << " ";
//    }

//    cout << endl;



    mark = abc[1].second;
    sz = abc[1].first;

    for (int i = 0 ; i < n ; i++){
        if (visited[i] == false){
            dfs3(i);
            if (comp.size() >= sz){
                        for (int i = 0 ; i < sz ; i++){
            ans[comp[i]] = mark;
        }

        mark = abc[2].second;

        for (int i = 0 ; i < n ; i++){
            res[i] = (ans[i] == 0 ? mark : ans[i]);
        }

        return res;

            }
            else comp.clear();
        }
    }

    vector<int> emptyy(n,0);

    return emptyy;


}

Compilation message

split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:88:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0 ; i < p.size() ; i++){
                      ~~^~~~~~~~~~
split.cpp:128:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if (comp.size() >= sz){
                 ~~~~~~~~~~~~^~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5120 KB ok, correct split
2 Correct 7 ms 5120 KB ok, correct split
3 Correct 8 ms 5120 KB ok, correct split
4 Correct 7 ms 5120 KB ok, correct split
5 Correct 7 ms 5120 KB ok, correct split
6 Correct 7 ms 5120 KB ok, correct split
7 Correct 105 ms 22260 KB ok, correct split
8 Correct 106 ms 19544 KB ok, correct split
9 Correct 127 ms 19056 KB ok, correct split
10 Correct 116 ms 22260 KB ok, correct split
11 Correct 107 ms 22612 KB ok, correct split

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5120 KB ok, correct split
2 Correct 7 ms 5120 KB ok, correct split
3 Correct 7 ms 5120 KB ok, correct split
4 Correct 137 ms 18012 KB ok, correct split
5 Correct 105 ms 13172 KB ok, correct split
6 Correct 123 ms 22260 KB ok, correct split
7 Correct 119 ms 19568 KB ok, correct split
8 Correct 153 ms 15860 KB ok, correct split
9 Correct 114 ms 14704 KB ok, correct split
10 Correct 59 ms 12272 KB ok, correct split
11 Correct 59 ms 12272 KB ok, correct split
12 Correct 62 ms 12272 KB ok, correct split

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5120 KB ok, correct split
2 Incorrect 107 ms 13304 KB jury found a solution, contestant did not
3 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5120 KB ok, correct split
2 Correct 7 ms 4992 KB ok, no valid answer
3 Correct 7 ms 5120 KB ok, correct split
4 Correct 8 ms 5152 KB ok, correct split
5 Correct 7 ms 5104 KB ok, correct split
6 Correct 7 ms 5120 KB ok, correct split
7 Correct 9 ms 5120 KB ok, correct split
8 Correct 7 ms 5120 KB ok, correct split
9 Correct 10 ms 5376 KB ok, correct split
10 Correct 10 ms 5376 KB ok, correct split
11 Correct 7 ms 5120 KB ok, correct split
12 Correct 10 ms 5376 KB ok, correct split
13 Correct 7 ms 5120 KB ok, correct split
14 Correct 7 ms 5120 KB ok, correct split
15 Correct 7 ms 5120 KB ok, correct split
16 Correct 7 ms 5120 KB ok, correct split
17 Correct 8 ms 5120 KB ok, correct split
18 Correct 7 ms 5120 KB ok, correct split
19 Correct 7 ms 5120 KB ok, correct split
20 Correct 9 ms 5376 KB ok, correct split
21 Correct 8 ms 5376 KB ok, correct split
22 Incorrect 10 ms 5248 KB jury found a solution, contestant did not
23 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5120 KB ok, correct split
2 Correct 7 ms 5120 KB ok, correct split
3 Correct 8 ms 5120 KB ok, correct split
4 Correct 7 ms 5120 KB ok, correct split
5 Correct 7 ms 5120 KB ok, correct split
6 Correct 7 ms 5120 KB ok, correct split
7 Correct 105 ms 22260 KB ok, correct split
8 Correct 106 ms 19544 KB ok, correct split
9 Correct 127 ms 19056 KB ok, correct split
10 Correct 116 ms 22260 KB ok, correct split
11 Correct 107 ms 22612 KB ok, correct split
12 Correct 8 ms 5120 KB ok, correct split
13 Correct 7 ms 5120 KB ok, correct split
14 Correct 7 ms 5120 KB ok, correct split
15 Correct 137 ms 18012 KB ok, correct split
16 Correct 105 ms 13172 KB ok, correct split
17 Correct 123 ms 22260 KB ok, correct split
18 Correct 119 ms 19568 KB ok, correct split
19 Correct 153 ms 15860 KB ok, correct split
20 Correct 114 ms 14704 KB ok, correct split
21 Correct 59 ms 12272 KB ok, correct split
22 Correct 59 ms 12272 KB ok, correct split
23 Correct 62 ms 12272 KB ok, correct split
24 Correct 7 ms 5120 KB ok, correct split
25 Incorrect 107 ms 13304 KB jury found a solution, contestant did not
26 Halted 0 ms 0 KB -