oj.uz

답안 #161741

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
161741 2019-11-04T10:20:44 Z andrew Split the Attractions (IOI19_split) C++17
7 / 100
 172 ms 34268 KB 
#include <bits/stdc++.h>
#include "split.h"

#define fi first
#define se second
#define pll pair<ll, ll>
#define pii pair<int, int>


using namespace std;
typedef long long ll;
typedef long double ld;
const ll MAXN = 1123456;
const ll N = 2e5;

vector <int> v[MAXN];

vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
    int m = p.size(), mx = 0;

    for(int i = 0; i < m; i++){
        v[p[i]].push_back(q[i]);
        v[q[i]].push_back(p[i]);
        mx = max(mx, (int)v[p[i]].size());
        mx = max(mx, (int)v[q[i]].size());
    }

    vector <int> res(n);
    if(a == 1){
        queue <int> q;
        int start = 0;
        for(int i = 0; i < n; i++)if(v[i].size() == 1)start = i;
        if(v[start].size() != 1){
            for(int i = 0; i < n; i++)if(v[i].size() != 2)start = i;
        }
        res[start] = 1;
        q.push(start);
        vector <bool> f(n);
        f[start] = 1;

        while(!q.empty()){
            int x = q.front();
            q.pop();
            if(x != start){
                if(!b)break;
                b--;
                res[x] = 2;
            }

            for(auto to : v[x])if(!f[to]){
                f[to] = 1;
                q.push(to);
            }
        }

        for(auto &i : res)if(!i)i = 3;
        return res;
    }else if(mx < 3){
        int F = 0, Last = 0;
        for(int i = 0; i < n; i++)if(v[i].size() == 1)F = i;
        int step = 1;
        vector <int> cnt(3);
        cnt[0] = a;
        cnt[1] = b;
        cnt[2] = c;
        for(int i = 0; i < n; i++){
            if(i){
                int New = 0;
                for(auto j : v[F])if(j != Last)New = j;
                Last = F;
                F = New;
            }
            while(!cnt[step - 1])step++;
            --cnt[step - 1];
            res[F] = step;
        }
        return res;
    }else{
        return res;
    }
	return res;
}

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 27 ms 26616 KB ok, correct split
2 Correct 26 ms 26616 KB ok, correct split
3 Correct 28 ms 26744 KB ok, correct split
4 Correct 28 ms 26744 KB ok, correct split
5 Correct 27 ms 26744 KB ok, correct split
6 Correct 27 ms 26616 KB ok, correct split
7 Correct 125 ms 31736 KB ok, correct split
8 Correct 125 ms 31864 KB ok, correct split
9 Correct 119 ms 31736 KB ok, correct split
10 Correct 99 ms 31776 KB ok, correct split
11 Correct 104 ms 31736 KB ok, correct split

Subtask #2
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 27 ms 26744 KB ok, correct split
2 Correct 27 ms 26744 KB ok, correct split
3 Correct 27 ms 26744 KB ok, correct split
4 Correct 127 ms 32888 KB ok, correct split
5 Correct 103 ms 31992 KB ok, correct split
6 Correct 99 ms 31748 KB ok, correct split
7 Correct 126 ms 31832 KB ok, correct split
8 Correct 172 ms 34268 KB ok, correct split
9 Incorrect 98 ms 31736 KB 2 components are not connected
10 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 27 ms 26616 KB jury found a solution, contestant did not
2 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 26 ms 26744 KB jury found a solution, contestant did not
2 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# 결과 실행 시간 메모리 Grader output
1 Correct 27 ms 26616 KB ok, correct split
2 Correct 26 ms 26616 KB ok, correct split
3 Correct 28 ms 26744 KB ok, correct split
4 Correct 28 ms 26744 KB ok, correct split
5 Correct 27 ms 26744 KB ok, correct split
6 Correct 27 ms 26616 KB ok, correct split
7 Correct 125 ms 31736 KB ok, correct split
8 Correct 125 ms 31864 KB ok, correct split
9 Correct 119 ms 31736 KB ok, correct split
10 Correct 99 ms 31776 KB ok, correct split
11 Correct 104 ms 31736 KB ok, correct split
12 Correct 27 ms 26744 KB ok, correct split
13 Correct 27 ms 26744 KB ok, correct split
14 Correct 27 ms 26744 KB ok, correct split
15 Correct 127 ms 32888 KB ok, correct split
16 Correct 103 ms 31992 KB ok, correct split
17 Correct 99 ms 31748 KB ok, correct split
18 Correct 126 ms 31832 KB ok, correct split
19 Correct 172 ms 34268 KB ok, correct split
20 Incorrect 98 ms 31736 KB 2 components are not connected
21 Halted 0 ms 0 KB -