oj.uz

답안 #168628

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
168628 2019-12-14T16:23:26 Z mhy908 Split the Attractions (IOI19_split) C++14
33 / 100
 166 ms 20344 KB 
#include "split.h"
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define F first
#define S second
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
typedef pair<LL, LL> pll;
const LL llinf=9000000000000000000;
const int inf=2000000000;
int n, m;
vector<int> temp[100010], link[100010];
vector<int> ans;
bool ch[100010];
int siz[100010], cen, c[100010];
void dfs1(int num){
    ch[num]=true;
    siz[num]=1;
    for(int i=0; i<temp[num].size(); i++){
        if(ch[temp[num][i]])continue;
        link[num].pb(temp[num][i]);
        link[temp[num][i]].pb(num);
        dfs1(temp[num][i]);
        siz[num]+=siz[temp[num][i]];
    }
}
void find_centroid(int num){
    if(ch[num])return;
    bool poss=true;
    ch[num]=true;
    for(int i=0; i<link[num].size(); i++){
        if(siz[link[num][i]]>n/2)poss=false;
    }
    if(poss){
        cen=num;
        return;
    }
    for(int i=0; i<link[num].size(); i++){
        int tt=siz[link[num][i]];
        siz[num]=n-tt;
        siz[link[num][i]]=n;
        find_centroid(link[num][i]);
        if(cen)return;
        siz[num]=n;
        siz[link[num][i]]=tt;
    }
}
void dfs2(int num, int col){
    if(num==cen||c[num])return;
    c[num]=col;
    for(int i=0; i<temp[num].size(); i++){
        dfs2(temp[num][i], col);
    }
}
int dp[100010];
int colored;
void dfs3(int num, int cnt, int p){
    if(colored>=cnt||ans[num]||num==cen)return;
    ans[num]=p;
    colored++;
    for(int i=0; i<temp[num].size(); i++){
        dfs3(temp[num][i], cnt, p);
    }
}
void dfs4(int num, int cnt, int p){
    if(colored>=cnt||ans[num])return;
    ans[num]=p;
    colored++;
    for(int i=0; i<temp[num].size(); i++){
        dfs4(temp[num][i], cnt, p);
    }
}
vector<int> find_split(int _n, int a, int b, int cc, vector<int> p, vector<int> q){
	n=_n, m=p.size();
	ans.resize(n);
	for(int i=0; i<m; i++){
        temp[p[i]].pb(q[i]);
        temp[q[i]].pb(p[i]);
	}
	dfs1(0);
	memset(ch, 0, sizeof(ch));
	find_centroid(0);
	int r=0;
	for(int i=0; i<link[cen].size(); i++){
        if(!c[link[cen][i]])dfs2(link[cen][i], ++r);
        dp[c[link[cen][i]]]+=siz[link[cen][i]];
	}
	bool flag=false;
	int tonum=0;
	for(int i=1; i<=r; i++){
        if(dp[i]>=min(min(a, b), cc)){
            flag=true;
            tonum=i;
        }
	}
	if(!flag)return ans;
	for(int i=0; i<link[cen].size(); i++){
        if(tonum==c[link[cen][i]]){
            if(a<=b&&a<=cc)dfs3(link[cen][i], a, 1);
            else if(b<=a&&b<=cc)dfs3(link[cen][i], b, 2);
            else dfs3(link[cen][i], cc, 3);
            break;
        }
	}
	colored=0;
	if(a<=b&&a<=cc){
        if(b<=cc)dfs4(cen, b, 2);
        else dfs4(cen, cc, 3);
	}
	else if(b<=a&&b<=cc){
        if(a<=cc)dfs4(cen, a, 1);
        else dfs4(cen, cc, 3);
	}
    else{
        if(a<=b)dfs4(cen, a, 1);
        dfs4(cen, cc, 3);
    }
    for(int i=0; i<n; i++){
        if(!ans[i]){
            if(a<=b&&a<=cc){
                if(b<=cc)ans[i]=3;
                else ans[i]=2;
            }
            else if(b<=a&&b<=cc){
                if(a<=cc)ans[i]=3;
                else ans[i]=1;
            }
            else{
                if(a<=b)ans[i]=2;
                ans[i]=1;
            }
        }
    }
    return ans;
}
/*
6 5 2 2 2
0 1
0 2
0 3
0 4
0 5
*/

Compilation message

split.cpp: In function 'void dfs1(int)':
split.cpp:21:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<temp[num].size(); i++){
                  ~^~~~~~~~~~~~~~~~~
split.cpp: In function 'void find_centroid(int)':
split.cpp:33:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<link[num].size(); i++){
                  ~^~~~~~~~~~~~~~~~~
split.cpp:40:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<link[num].size(); i++){
                  ~^~~~~~~~~~~~~~~~~
split.cpp: In function 'void dfs2(int, int)':
split.cpp:53:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<temp[num].size(); i++){
                  ~^~~~~~~~~~~~~~~~~
split.cpp: In function 'void dfs3(int, int, int)':
split.cpp:63:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<temp[num].size(); i++){
                  ~^~~~~~~~~~~~~~~~~
split.cpp: In function 'void dfs4(int, int, int)':
split.cpp:71:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<temp[num].size(); i++){
                  ~^~~~~~~~~~~~~~~~~
split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:86:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<link[cen].size(); i++){
               ~^~~~~~~~~~~~~~~~~
split.cpp:99:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<link[cen].size(); i++){
               ~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 5112 KB ok, correct split
2 Correct 6 ms 5112 KB ok, correct split
3 Correct 6 ms 5112 KB ok, correct split
4 Correct 6 ms 5112 KB ok, correct split
5 Correct 6 ms 5112 KB ok, correct split
6 Correct 6 ms 5112 KB ok, correct split
7 Correct 149 ms 20216 KB ok, correct split
8 Correct 130 ms 18780 KB ok, correct split
9 Incorrect 151 ms 18396 KB invalid split: #1=99998, #2=0, #3=2
10 Halted 0 ms 0 KB -

Subtask #2
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 5112 KB ok, correct split
2 Correct 7 ms 5136 KB ok, correct split
3 Correct 6 ms 5112 KB ok, correct split
4 Correct 158 ms 19512 KB ok, correct split
5 Correct 139 ms 15864 KB ok, correct split
6 Correct 144 ms 20344 KB ok, correct split
7 Correct 140 ms 18680 KB ok, correct split
8 Correct 166 ms 18780 KB ok, correct split
9 Correct 143 ms 15728 KB ok, correct split
10 Correct 87 ms 16496 KB ok, correct split
11 Correct 108 ms 16496 KB ok, correct split
12 Correct 94 ms 16880 KB ok, correct split

Subtask #3
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 5112 KB ok, correct split
2 Correct 122 ms 15944 KB ok, correct split
3 Correct 44 ms 9464 KB ok, correct split
4 Correct 6 ms 5112 KB ok, correct split
5 Correct 144 ms 17236 KB ok, correct split
6 Correct 141 ms 17116 KB ok, correct split
7 Correct 136 ms 17144 KB ok, correct split
8 Correct 135 ms 17756 KB ok, correct split
9 Correct 130 ms 17144 KB ok, correct split
10 Correct 37 ms 8696 KB ok, no valid answer
11 Correct 52 ms 10492 KB ok, no valid answer
12 Correct 101 ms 16432 KB ok, no valid answer
13 Correct 122 ms 16064 KB ok, no valid answer
14 Correct 90 ms 16900 KB ok, no valid answer

Subtask #4
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 5112 KB ok, correct split
2 Correct 6 ms 5112 KB ok, no valid answer
3 Correct 6 ms 5112 KB ok, correct split
4 Correct 6 ms 5112 KB ok, correct split
5 Correct 6 ms 5112 KB ok, correct split
6 Correct 6 ms 5112 KB ok, correct split
7 Correct 6 ms 5112 KB ok, correct split
8 Correct 6 ms 5112 KB ok, correct split
9 Correct 9 ms 5496 KB ok, correct split
10 Correct 9 ms 5468 KB ok, correct split
11 Correct 6 ms 5112 KB ok, correct split
12 Incorrect 9 ms 5496 KB invalid split: #1=800, #2=1595, #3=6
13 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 5112 KB ok, correct split
2 Correct 6 ms 5112 KB ok, correct split
3 Correct 6 ms 5112 KB ok, correct split
4 Correct 6 ms 5112 KB ok, correct split
5 Correct 6 ms 5112 KB ok, correct split
6 Correct 6 ms 5112 KB ok, correct split
7 Correct 149 ms 20216 KB ok, correct split
8 Correct 130 ms 18780 KB ok, correct split
9 Incorrect 151 ms 18396 KB invalid split: #1=99998, #2=0, #3=2
10 Halted 0 ms 0 KB -