oj.uz

Submission #233202

# Submission time Handle Problem Language Result Execution time Memory
233202 2020-05-19T22:27:39 Z UserIsUndefined Split the Attractions (IOI19_split) C++14
18 / 100
 160 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){
                break;
            }
            else comp.clear();
        }
    }

    if (comp.size() < sz){
        vector<int> em(n,0);
        return em;
    }

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

    }




}

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){
                 ~~~~~~~~~~~~^~~~~
split.cpp:134:21: 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 8 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 114 ms 19572 KB ok, correct split
9 Correct 125 ms 19160 KB ok, correct split
10 Correct 125 ms 22132 KB ok, correct split
11 Correct 130 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 5120 KB ok, correct split
3 Correct 7 ms 5168 KB ok, correct split
4 Correct 143 ms 18164 KB ok, correct split
5 Correct 101 ms 13280 KB ok, correct split
6 Correct 114 ms 22260 KB ok, correct split
7 Correct 108 ms 19572 KB ok, correct split
8 Correct 160 ms 15860 KB ok, correct split
9 Correct 102 ms 14708 KB ok, correct split
10 Correct 56 ms 12272 KB ok, correct split
11 Correct 60 ms 12276 KB ok, correct split
12 Correct 57 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 13484 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 8 ms 5120 KB ok, correct split
7 Correct 7 ms 5120 KB ok, correct split
8 Correct 8 ms 5120 KB ok, correct split
9 Correct 10 ms 5480 KB ok, correct split
10 Correct 10 ms 5504 KB ok, correct split
11 Correct 8 ms 5120 KB ok, correct split
12 Correct 10 ms 5376 KB ok, correct split
13 Correct 8 ms 5120 KB ok, correct split
14 Correct 8 ms 5120 KB ok, correct split
15 Correct 7 ms 5120 KB ok, correct split
16 Correct 7 ms 5248 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 5120 KB ok, correct split
20 Correct 8 ms 5248 KB ok, correct split
21 Correct 8 ms 5376 KB ok, correct split
22 Incorrect 9 ms 5376 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 8 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 114 ms 19572 KB ok, correct split
9 Correct 125 ms 19160 KB ok, correct split
10 Correct 125 ms 22132 KB ok, correct split
11 Correct 130 ms 22644 KB ok, correct split
12 Correct 7 ms 5120 KB ok, correct split
13 Correct 7 ms 5120 KB ok, correct split
14 Correct 7 ms 5168 KB ok, correct split
15 Correct 143 ms 18164 KB ok, correct split
16 Correct 101 ms 13280 KB ok, correct split
17 Correct 114 ms 22260 KB ok, correct split
18 Correct 108 ms 19572 KB ok, correct split
19 Correct 160 ms 15860 KB ok, correct split
20 Correct 102 ms 14708 KB ok, correct split
21 Correct 56 ms 12272 KB ok, correct split
22 Correct 60 ms 12276 KB ok, correct split
23 Correct 57 ms 12272 KB ok, correct split
24 Correct 7 ms 5120 KB ok, correct split
25 Incorrect 107 ms 13484 KB jury found a solution, contestant did not
26 Halted 0 ms 0 KB -