oj.uz

Submission #233211

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


}

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){
                 ~~~~~~~~~~~~^~~~~
split.cpp:147:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

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 107 ms 22260 KB ok, correct split
8 Correct 119 ms 19604 KB ok, correct split
9 Correct 108 ms 19184 KB ok, correct split
10 Correct 110 ms 22388 KB ok, correct split
11 Correct 122 ms 22516 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 8 ms 5120 KB ok, correct split
4 Correct 128 ms 18036 KB ok, correct split
5 Correct 106 ms 13276 KB ok, correct split
6 Correct 106 ms 22260 KB ok, correct split
7 Correct 108 ms 19568 KB ok, correct split
8 Correct 146 ms 15860 KB ok, correct split
9 Correct 105 ms 14704 KB ok, correct split
10 Correct 58 ms 12272 KB ok, correct split
11 Correct 59 ms 12272 KB ok, correct split
12 Correct 61 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 79 ms 12920 KB WA in grader: Invalid length of the result.
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 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 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 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 8 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 7 ms 5120 KB ok, correct split
20 Correct 8 ms 5248 KB ok, correct split
21 Correct 9 ms 5376 KB ok, correct split
22 Incorrect 9 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 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 107 ms 22260 KB ok, correct split
8 Correct 119 ms 19604 KB ok, correct split
9 Correct 108 ms 19184 KB ok, correct split
10 Correct 110 ms 22388 KB ok, correct split
11 Correct 122 ms 22516 KB ok, correct split
12 Correct 7 ms 5120 KB ok, correct split
13 Correct 7 ms 5120 KB ok, correct split
14 Correct 8 ms 5120 KB ok, correct split
15 Correct 128 ms 18036 KB ok, correct split
16 Correct 106 ms 13276 KB ok, correct split
17 Correct 106 ms 22260 KB ok, correct split
18 Correct 108 ms 19568 KB ok, correct split
19 Correct 146 ms 15860 KB ok, correct split
20 Correct 105 ms 14704 KB ok, correct split
21 Correct 58 ms 12272 KB ok, correct split
22 Correct 59 ms 12272 KB ok, correct split
23 Correct 61 ms 12272 KB ok, correct split
24 Correct 7 ms 5120 KB ok, correct split
25 Incorrect 79 ms 12920 KB WA in grader: Invalid length of the result.
26 Halted 0 ms 0 KB -