oj.uz

Submission #232719

# Submission time Handle Problem Language Result Execution time Memory
232719 2020-05-17T23:02:01 Z UserIsUndefined Split the Attractions (IOI19_split) C++14
0 / 100
 8 ms 5120 KB 
#include <bits/stdc++.h>
#include "split.h"

using namespace std;


vector<int> adj[100005];
vector<int> adj2[100005];

map<int,int> visited;
int children[100005];
vector<pair<int,int>> childidx;
int ans[100005];
int now, sz;


void counter(int s){
    visited[s] = true;

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

    children[s]++;

}





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

    for (int i : adj2[v]){
        if ((visited[i] == false)&&(sz)){
            sz--;
            dfs(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);
    }

    counter(0);


    for (int i = 0 ; i < n ; i++){
        childidx.push_back({children[i], i});
    }

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


    visited.clear();

    int past = 0;

    for (int i = 0 ; i < 2 ; i++){
        now = abc[i].second;
        sz = abc[i].first;
        sz--;

        for (int j = past ; j < n ; j++){
            if (childidx[j].first >= sz){
                dfs(childidx[j].second);
                past = j + 1;
                break;
            }
        }

    }

    for (int i = 0 ; i < n ; i++){
        res[i] = (ans[i] == 0 ? abc[2].second : 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:63: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 7 ms 4992 KB ok, correct split
2 Correct 7 ms 4992 KB ok, correct split
3 Correct 7 ms 4992 KB ok, correct split
4 Correct 7 ms 4992 KB ok, correct split
5 Correct 7 ms 4992 KB ok, correct split
6 Incorrect 7 ms 5120 KB invalid split: #1=20, #2=19, #3=61
7 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4992 KB ok, correct split
2 Correct 7 ms 4992 KB ok, correct split
3 Incorrect 7 ms 4992 KB invalid split: #1=1, #2=1, #3=3
4 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 4992 KB invalid split: #1=1, #2=1, #3=3
2 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 4992 KB invalid split: #1=6, #2=1, #3=2
2 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4992 KB ok, correct split
2 Correct 7 ms 4992 KB ok, correct split
3 Correct 7 ms 4992 KB ok, correct split
4 Correct 7 ms 4992 KB ok, correct split
5 Correct 7 ms 4992 KB ok, correct split
6 Incorrect 7 ms 5120 KB invalid split: #1=20, #2=19, #3=61
7 Halted 0 ms 0 KB -