oj.uz

Submission #168632

# Submission time Handle Problem Language Result Execution time Memory
168632 2019-12-14T16:28:43 Z mhy908 Split the Attractions (IOI19_split) C++14
33 / 100
 225 ms 19364 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, b, 2);
    }
    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

# Verdict Execution time Memory 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 131 ms 18936 KB ok, correct split
8 Correct 173 ms 17572 KB ok, correct split
9 Incorrect 144 ms 17156 KB invalid split: #1=99998, #2=0, #3=2
10 Halted 0 ms 0 KB -

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 KB ok, correct split
2 Correct 6 ms 5084 KB ok, correct split
3 Correct 6 ms 5112 KB ok, correct split
4 Correct 172 ms 17864 KB ok, correct split
5 Correct 122 ms 14712 KB ok, correct split
6 Correct 145 ms 19364 KB ok, correct split
7 Correct 225 ms 17528 KB ok, correct split
8 Correct 167 ms 16504 KB ok, correct split
9 Correct 139 ms 14584 KB ok, correct split
10 Correct 93 ms 15728 KB ok, correct split
11 Correct 91 ms 15636 KB ok, correct split
12 Correct 95 ms 15728 KB ok, correct split

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 KB ok, correct split
2 Correct 122 ms 14716 KB ok, correct split
3 Correct 45 ms 9004 KB ok, correct split
4 Correct 6 ms 5112 KB ok, correct split
5 Correct 138 ms 16120 KB ok, correct split
6 Correct 129 ms 15864 KB ok, correct split
7 Correct 150 ms 15864 KB ok, correct split
8 Correct 153 ms 16676 KB ok, correct split
9 Correct 204 ms 15864 KB ok, correct split
10 Correct 42 ms 8312 KB ok, no valid answer
11 Correct 72 ms 9976 KB ok, no valid answer
12 Correct 135 ms 15320 KB ok, no valid answer
13 Correct 112 ms 14840 KB ok, no valid answer
14 Correct 87 ms 15680 KB ok, no valid answer

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 KB ok, correct split
2 Correct 6 ms 5116 KB ok, no valid answer
3 Correct 6 ms 5240 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 5136 KB ok, correct split
9 Correct 9 ms 5496 KB ok, correct split
10 Correct 9 ms 5368 KB ok, correct split
11 Correct 6 ms 5116 KB ok, correct split
12 Incorrect 9 ms 5368 KB invalid split: #1=800, #2=1595, #3=6
13 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory 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 131 ms 18936 KB ok, correct split
8 Correct 173 ms 17572 KB ok, correct split
9 Incorrect 144 ms 17156 KB invalid split: #1=99998, #2=0, #3=2
10 Halted 0 ms 0 KB -