oj.uz

답안 #233204

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
233204 2020-05-19T22:29:10 Z UserIsUndefined Split the Attractions (IOI19_split) C++14
18 / 100
 141 ms 25976 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){
                 ~~~~~~~~~~~~^~~~~

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 5268 KB ok, correct split
2 Correct 7 ms 5120 KB ok, correct split
3 Correct 8 ms 5120 KB ok, correct split
4 Correct 8 ms 5248 KB ok, correct split
5 Correct 7 ms 5120 KB ok, correct split
6 Correct 7 ms 5120 KB ok, correct split
7 Correct 104 ms 22132 KB ok, correct split
8 Correct 111 ms 19572 KB ok, correct split
9 Correct 110 ms 19056 KB ok, correct split
10 Correct 106 ms 22132 KB ok, correct split
11 Correct 113 ms 22624 KB ok, correct split

Subtask #2
11.0 / 11.0

# 결과 실행 시간 메모리 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 128 ms 18060 KB ok, correct split
5 Correct 100 ms 13192 KB ok, correct split
6 Correct 112 ms 22388 KB ok, correct split
7 Correct 106 ms 19696 KB ok, correct split
8 Correct 141 ms 15916 KB ok, correct split
9 Correct 106 ms 14704 KB ok, correct split
10 Correct 57 ms 12272 KB ok, correct split
11 Correct 57 ms 12280 KB ok, correct split
12 Correct 58 ms 12272 KB ok, correct split

Subtask #3
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 5120 KB ok, correct split
2 Runtime error 99 ms 25976 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 5120 KB ok, correct split
2 Incorrect 7 ms 5120 KB invalid split: #1=1, #2=2, #3=3
3 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 5268 KB ok, correct split
2 Correct 7 ms 5120 KB ok, correct split
3 Correct 8 ms 5120 KB ok, correct split
4 Correct 8 ms 5248 KB ok, correct split
5 Correct 7 ms 5120 KB ok, correct split
6 Correct 7 ms 5120 KB ok, correct split
7 Correct 104 ms 22132 KB ok, correct split
8 Correct 111 ms 19572 KB ok, correct split
9 Correct 110 ms 19056 KB ok, correct split
10 Correct 106 ms 22132 KB ok, correct split
11 Correct 113 ms 22624 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 5120 KB ok, correct split
15 Correct 128 ms 18060 KB ok, correct split
16 Correct 100 ms 13192 KB ok, correct split
17 Correct 112 ms 22388 KB ok, correct split
18 Correct 106 ms 19696 KB ok, correct split
19 Correct 141 ms 15916 KB ok, correct split
20 Correct 106 ms 14704 KB ok, correct split
21 Correct 57 ms 12272 KB ok, correct split
22 Correct 57 ms 12280 KB ok, correct split
23 Correct 58 ms 12272 KB ok, correct split
24 Correct 7 ms 5120 KB ok, correct split
25 Runtime error 99 ms 25976 KB Execution killed with signal 11 (could be triggered by violating memory limits)
26 Halted 0 ms 0 KB -