oj.uz

Submission #233206

# Submission time Handle Problem Language Result Execution time Memory
233206 2020-05-19T22:30:48 Z UserIsUndefined Split the Attractions (IOI19_split) C++14
18 / 100
 146 ms 22644 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;

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)){
        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;

    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:87:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0 ; i < p.size() ; i++){
                      ~~^~~~~~~~~~
split.cpp:127: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 7 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 111 ms 22260 KB ok, correct split
8 Correct 108 ms 19576 KB ok, correct split
9 Correct 118 ms 19316 KB ok, correct split
10 Correct 104 ms 22260 KB ok, correct split
11 Correct 105 ms 22644 KB ok, correct split

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5120 KB ok, correct split
2 Correct 7 ms 5248 KB ok, correct split
3 Correct 7 ms 5120 KB ok, correct split
4 Correct 125 ms 18036 KB ok, correct split
5 Correct 90 ms 13300 KB ok, correct split
6 Correct 105 ms 22260 KB ok, correct split
7 Correct 112 ms 19696 KB ok, correct split
8 Correct 146 ms 15988 KB ok, correct split
9 Correct 102 ms 14708 KB ok, correct split
10 Correct 59 ms 12280 KB ok, correct split
11 Correct 73 ms 12272 KB ok, correct split
12 Correct 58 ms 12280 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 95 ms 13432 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 5120 KB ok, no valid answer
3 Correct 7 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 7 ms 5120 KB ok, correct split
8 Correct 7 ms 5120 KB ok, correct split
9 Correct 9 ms 5376 KB ok, correct split
10 Correct 10 ms 5504 KB ok, correct split
11 Correct 7 ms 5120 KB ok, correct split
12 Correct 9 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 7 ms 5120 KB ok, correct split
18 Correct 7 ms 5120 KB ok, correct split
19 Correct 8 ms 5248 KB ok, correct split
20 Correct 8 ms 5248 KB ok, correct split
21 Correct 10 ms 5376 KB ok, correct split
22 Incorrect 9 ms 5504 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 7 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 111 ms 22260 KB ok, correct split
8 Correct 108 ms 19576 KB ok, correct split
9 Correct 118 ms 19316 KB ok, correct split
10 Correct 104 ms 22260 KB ok, correct split
11 Correct 105 ms 22644 KB ok, correct split
12 Correct 7 ms 5120 KB ok, correct split
13 Correct 7 ms 5248 KB ok, correct split
14 Correct 7 ms 5120 KB ok, correct split
15 Correct 125 ms 18036 KB ok, correct split
16 Correct 90 ms 13300 KB ok, correct split
17 Correct 105 ms 22260 KB ok, correct split
18 Correct 112 ms 19696 KB ok, correct split
19 Correct 146 ms 15988 KB ok, correct split
20 Correct 102 ms 14708 KB ok, correct split
21 Correct 59 ms 12280 KB ok, correct split
22 Correct 73 ms 12272 KB ok, correct split
23 Correct 58 ms 12280 KB ok, correct split
24 Correct 7 ms 5120 KB ok, correct split
25 Incorrect 95 ms 13432 KB jury found a solution, contestant did not
26 Halted 0 ms 0 KB -