oj.uz

Submission #233218

# Submission time Handle Problem Language Result Execution time Memory
233218 2020-05-20T00:10:24 Z UserIsUndefined Split the Attractions (IOI19_split) C++14
11 / 100
 2000 ms 103364 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 sz;
bool ok;
int doo;
int nn;
int now;


void mark(int v){
    ans[v] = now;

    for (int i : adj[v]){
        if ((ans[i] == 0)&&(sz)){
            sz--;
            mark(i);
        }
    }

}



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

    children[v]++;



}






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



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

        int sizex = 0 ; int sizey = 0;

        visited[x] = true;
        visited[y] = true;

        sz = 0;
        dfs(x);
        sizex = sz;
        sizey = n - sz;
        memset(visited , 0 , sizeof visited);
        if (sizex > sizey){swap(sizex , sizey); swap(x , y);}

        if ((sizex >= abc[0].first)&&(sizey >= abc[1].first)){
            now = abc[0].second;
            sz = abc[0].first;

            ans[x] = now;
            ans[y] = abc[1].second;
            sz--;

            mark(x);

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

            sz--;

            mark(y);

            for (int i = 0 ; i < n ; i++){
                res[i] = (ans[i] == 0 ? abc[2].second : ans[i]);
            }

            return res;


        }


    }

    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:66:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0 ; i < p.size() ; i++){
                      ~~^~~~~~~~~~
split.cpp:75:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0 ; i < p.size() ; i++){
                      ~~^~~~~~~~~~

Subtask #1
0 / 7.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 8 ms 5120 KB ok, correct split
5 Correct 8 ms 5120 KB ok, correct split
6 Incorrect 8 ms 5248 KB jury found a solution, contestant did not
7 Halted 0 ms 0 KB -

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5120 KB ok, correct split
2 Correct 10 ms 5120 KB ok, correct split
3 Correct 7 ms 5120 KB ok, correct split
4 Correct 119 ms 18424 KB ok, correct split
5 Correct 71 ms 11896 KB ok, correct split
6 Correct 112 ms 21112 KB ok, correct split
7 Correct 95 ms 14584 KB ok, correct split
8 Correct 169 ms 17656 KB ok, correct split
9 Correct 107 ms 15352 KB ok, correct split
10 Correct 56 ms 11760 KB ok, correct split
11 Correct 58 ms 12656 KB ok, correct split
12 Correct 58 ms 12164 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 Execution timed out 2086 ms 103364 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 5120 KB jury found a solution, contestant did not
2 Halted 0 ms 0 KB -

Subtask #5
0 / 36.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 8 ms 5120 KB ok, correct split
5 Correct 8 ms 5120 KB ok, correct split
6 Incorrect 8 ms 5248 KB jury found a solution, contestant did not
7 Halted 0 ms 0 KB -