oj.uz

답안 #815037

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
815037 2023-08-08T11:53:13 Z physics07 Split the Attractions (IOI19_split) C++17
18 / 100
 110 ms 23448 KB 
#include "split.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<int> adj[100001], tree[100001];
bool visited[100001];
int sz[100001], n, c, cc[100001];
int dfs_tree(int x) {
    visited[x]=1;
    sz[x]=1;
    for(auto i: adj[x]) if(!visited[i]) {
        tree[x].push_back(i);
        tree[i].push_back(x);
        sz[x]+=dfs_tree(i);
    }
    return sz[x];
}
int centroid(int x) {
    visited[x]=1;
    for(auto i: tree[x]) if(!visited[i] && sz[i]*2>n) return centroid(i);
    return x;
}
int sol(int x) {
    visited[x]=1;
    cc[x]=1;
    for(auto i: adj[x]) if(!visited[i] && i!=c) cc[x]+=sol(i);
    return cc[x];
}
vector<int> ans;
int cnt;
void get_all(int x, int p, int avoid=-1) {
    visited[x]=1;
    ans[x]=p;
    cnt--;
    if(cnt<=0) return;
    for(auto i: adj[x]) if(!visited[i] && i!=avoid) {
        get_all(i, p, avoid);
        if(cnt<=0) return;
    }
}
vector<int> find_split(int N, int A, int B, int C, vector<int> p, vector<int> q) {
    n=N;
    vector<pair<int, int>> v;
    v.push_back({A, 1});
    v.push_back({B, 2});
    v.push_back({C, 3});
    sort(v.begin(), v.end());
    int a=v[0].first, b=v[1].first, c=v[2].first;
    int color[]={v[0].second, v[1].second, v[2].second};
    for(int i=0; i<n; i++) ans.push_back(0);
    int m=(int)p.size();
    for(int i=0; i<m; i++) {
        adj[p[i]].push_back(q[i]);
        adj[q[i]].push_back(p[i]);
    }
    dfs_tree(0);
    memset(visited, 0, sizeof(visited));
    c=centroid(0);
    memset(visited, 0, sizeof(visited));
    bool flag=0;
    int idx=0;
    for(int i=0; i<n; i++) if(!visited[i] && i!=c) {
        if(sol(i)>=a) {
            flag=1;
            idx=i;
            break;
        }
    }
    if(!flag) return ans;
    memset(visited, 0, sizeof(visited));
    cnt=a;
    get_all(idx, color[0], c);
    cnt=b;
    get_all(c, color[1]);
    for(int i=0; i<n; i++) if(!ans[i]) ans[i]=color[2];
    return ans;
}

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 5076 KB ok, correct split
2 Correct 2 ms 5076 KB ok, correct split
3 Correct 2 ms 5076 KB ok, correct split
4 Correct 3 ms 5076 KB ok, correct split
5 Correct 3 ms 5000 KB ok, correct split
6 Correct 2 ms 5076 KB ok, correct split
7 Correct 95 ms 22304 KB ok, correct split
8 Correct 91 ms 20828 KB ok, correct split
9 Correct 110 ms 20140 KB ok, correct split
10 Correct 84 ms 23356 KB ok, correct split
11 Correct 68 ms 23448 KB ok, correct split

Subtask #2
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 5000 KB ok, correct split
2 Correct 2 ms 5000 KB ok, correct split
3 Correct 2 ms 5004 KB ok, correct split
4 Correct 102 ms 20592 KB ok, correct split
5 Correct 64 ms 15856 KB ok, correct split
6 Correct 86 ms 23432 KB ok, correct split
7 Correct 98 ms 20608 KB ok, correct split
8 Correct 80 ms 18016 KB ok, correct split
9 Correct 56 ms 15624 KB ok, correct split
10 Correct 44 ms 15620 KB ok, correct split
11 Correct 43 ms 16036 KB ok, correct split
12 Correct 52 ms 16324 KB ok, correct split

Subtask #3
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 5000 KB ok, correct split
2 Correct 62 ms 15804 KB ok, correct split
3 Correct 32 ms 9348 KB ok, correct split
4 Incorrect 3 ms 5076 KB invalid split: #1=9, #2=24, #3=33
5 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 5076 KB ok, correct split
2 Correct 3 ms 5076 KB ok, no valid answer
3 Correct 2 ms 5000 KB ok, correct split
4 Correct 2 ms 5076 KB ok, correct split
5 Correct 3 ms 5076 KB ok, correct split
6 Correct 4 ms 5092 KB ok, correct split
7 Incorrect 2 ms 5076 KB invalid split: #1=1, #2=4, #3=7
8 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 5076 KB ok, correct split
2 Correct 2 ms 5076 KB ok, correct split
3 Correct 2 ms 5076 KB ok, correct split
4 Correct 3 ms 5076 KB ok, correct split
5 Correct 3 ms 5000 KB ok, correct split
6 Correct 2 ms 5076 KB ok, correct split
7 Correct 95 ms 22304 KB ok, correct split
8 Correct 91 ms 20828 KB ok, correct split
9 Correct 110 ms 20140 KB ok, correct split
10 Correct 84 ms 23356 KB ok, correct split
11 Correct 68 ms 23448 KB ok, correct split
12 Correct 3 ms 5000 KB ok, correct split
13 Correct 2 ms 5000 KB ok, correct split
14 Correct 2 ms 5004 KB ok, correct split
15 Correct 102 ms 20592 KB ok, correct split
16 Correct 64 ms 15856 KB ok, correct split
17 Correct 86 ms 23432 KB ok, correct split
18 Correct 98 ms 20608 KB ok, correct split
19 Correct 80 ms 18016 KB ok, correct split
20 Correct 56 ms 15624 KB ok, correct split
21 Correct 44 ms 15620 KB ok, correct split
22 Correct 43 ms 16036 KB ok, correct split
23 Correct 52 ms 16324 KB ok, correct split
24 Correct 3 ms 5000 KB ok, correct split
25 Correct 62 ms 15804 KB ok, correct split
26 Correct 32 ms 9348 KB ok, correct split
27 Incorrect 3 ms 5076 KB invalid split: #1=9, #2=24, #3=33
28 Halted 0 ms 0 KB -