oj.uz

Submission #232720

# Submission time Handle Problem Language Result Execution time Memory
232720 2020-05-17T23:47:21 Z UserIsUndefined Split the Attractions (IOI19_split) C++14
18 / 100
 502 ms 23676 KB 
#include <bits/stdc++.h>
#include "split.h"

using namespace std;


vector<int> adj[100005];


map<int,int> visited;
int children[100005];
int timein[100005];
int timeout[100005];
int timee;

int ans[100005];
int sett, sz;

int F , maxx;


void getF(int v , int p){
    visited[v] = true;
    if (p > maxx){
        p = maxx;
        F = v;
    }

    for (int i : adj[v]){
        if (visited[i] == false){
            getF(i , p + 1);
        }
    }


}



void go(int v){
    visited[v] = true;
    timee++;
    timein[v] = timee;

    for (int i : adj[v]){
        if (visited[i] == false){
            go(i);
            children[v] += children[i];
        }
    }
    timee++;
    timeout[v] = timee;
    children[v]++;


}












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

    for (int i : adj[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);
    }

    F = 0;
    maxx = 0;

    getF(0 , 0);


//    cout << "first away ? :" << F <<endl;

    visited.clear();

    maxx = 0;

    getF(F, 0);
//
//    cout << "second away ? :" << F <<endl;

    visited.clear();

    go(F);

    visited.clear();

    sett = abc[0].second;
    sz = abc[0].first;
    int minn = 1e9;
    int indx = -1;

    for (int i = 0 ; i < n ; i++){
        if (children[i] >= sz){
            if (children[i] < minn){
                minn = children[i];
                indx = i;
            }
        }
    }


    int cont = 0;

    for (int i = 0 ; i < n ; i++){
        if ((timein[i] >= timein[indx])&&(timeout[i] <= timeout[indx])){
            visited[i] = true;
            res[i] = sett;
            cont++;
        }
        if (cont == sz)break;
    }




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

    for (int i = 0 ; i < n ; i++){
        if (visited[i] == false){
            sz--;
            dfs(i);
            if (sz == 0)break;
            else sz = abc[1].second;
        }
    }

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


    map<int,int> should;
    for (int i = 0 ; i < 3 ; i++){
        should[abc[i].second] = abc[i].first;
    }

    map<int,int> ex;

    for (int i = 0 ; i < n ; i++){
        ex[res[i]]++;
    }

    for (int i = 1 ; i <= 3;i++){
        if (ex[i] != should[i]){
            vector<int> empy(n,0);
            return empy;
        }
    }


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

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2688 KB ok, correct split
2 Correct 5 ms 2688 KB ok, correct split
3 Correct 5 ms 2688 KB ok, correct split
4 Correct 5 ms 2688 KB ok, correct split
5 Correct 6 ms 2688 KB ok, correct split
6 Correct 6 ms 2688 KB ok, correct split
7 Correct 429 ms 23432 KB ok, correct split
8 Correct 346 ms 23032 KB ok, correct split
9 Correct 408 ms 23416 KB ok, correct split
10 Correct 354 ms 22912 KB ok, correct split
11 Correct 396 ms 23544 KB ok, correct split

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2688 KB ok, correct split
2 Correct 5 ms 2688 KB ok, correct split
3 Correct 6 ms 2688 KB ok, correct split
4 Correct 483 ms 19064 KB ok, correct split
5 Correct 348 ms 14200 KB ok, correct split
6 Correct 353 ms 23032 KB ok, correct split
7 Correct 393 ms 23676 KB ok, correct split
8 Correct 502 ms 16376 KB ok, correct split
9 Correct 393 ms 14260 KB ok, correct split
10 Correct 303 ms 14576 KB ok, correct split
11 Correct 299 ms 14432 KB ok, correct split
12 Correct 266 ms 14460 KB ok, correct split

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2688 KB ok, correct split
2 Incorrect 331 ms 14568 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 6 ms 2688 KB ok, correct split
2 Correct 6 ms 2688 KB ok, no valid answer
3 Correct 6 ms 2688 KB ok, correct split
4 Correct 6 ms 2688 KB ok, correct split
5 Correct 6 ms 2688 KB ok, correct split
6 Correct 6 ms 2688 KB ok, correct split
7 Correct 6 ms 2688 KB ok, correct split
8 Correct 6 ms 2688 KB ok, correct split
9 Correct 12 ms 3200 KB ok, correct split
10 Correct 12 ms 3072 KB ok, correct split
11 Correct 7 ms 2688 KB ok, correct split
12 Incorrect 12 ms 3072 KB 2 components are not connected
13 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2688 KB ok, correct split
2 Correct 5 ms 2688 KB ok, correct split
3 Correct 5 ms 2688 KB ok, correct split
4 Correct 5 ms 2688 KB ok, correct split
5 Correct 6 ms 2688 KB ok, correct split
6 Correct 6 ms 2688 KB ok, correct split
7 Correct 429 ms 23432 KB ok, correct split
8 Correct 346 ms 23032 KB ok, correct split
9 Correct 408 ms 23416 KB ok, correct split
10 Correct 354 ms 22912 KB ok, correct split
11 Correct 396 ms 23544 KB ok, correct split
12 Correct 6 ms 2688 KB ok, correct split
13 Correct 5 ms 2688 KB ok, correct split
14 Correct 6 ms 2688 KB ok, correct split
15 Correct 483 ms 19064 KB ok, correct split
16 Correct 348 ms 14200 KB ok, correct split
17 Correct 353 ms 23032 KB ok, correct split
18 Correct 393 ms 23676 KB ok, correct split
19 Correct 502 ms 16376 KB ok, correct split
20 Correct 393 ms 14260 KB ok, correct split
21 Correct 303 ms 14576 KB ok, correct split
22 Correct 299 ms 14432 KB ok, correct split
23 Correct 266 ms 14460 KB ok, correct split
24 Correct 6 ms 2688 KB ok, correct split
25 Incorrect 331 ms 14568 KB jury found a solution, contestant did not
26 Halted 0 ms 0 KB -