oj.uz

Submission #548485

# Submission time Handle Problem Language Result Execution time Memory
548485 2022-04-13T14:12:01 Z Khizri Split the Attractions (IOI19_split) C++17
18 / 100
 84 ms 18952 KB 
#include "split.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define F first
#define S second
#define INF 1e18
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define pii pair<int,int>
#define pll pair<ll,ll>
#define OK cout<<"Ok"<<endl;
const int mxn=2e5+5;
int d[mxn],color[mxn],x,q,k,sum[mxn],res,pp,say,xx,yy,N;
vector<int>vt[mxn];
vector<int>v;
bool ok=false;
void dfs3(int u,int p,int k){
    if(say){
        say--;
        color[u]=k;
    }
    for(int v:vt[u]){
        if(v!=p&&!color[v]){
            dfs3(v,u,k);
        }
    }
}
void dfs(int u,int p){
    sum[u]=1;
    for(int v:vt[u]){
        if(v!=p){
            dfs(v,u);
            sum[u]+=sum[v];
        }
    }
    if(sum[u]>=xx&&N-sum[u]>=xx&&!ok){
        ok=true;
        res=u;
        pp=p;
    }
}
void dfs(int u){
    v.pb(u);
    color[u]=1;
    for(int v:vt[u]){
        if(!color[v]){
            dfs(v);
        }
    }
}
void dfs2(int u){
    k--;
    if(k==0){
        color[u]=2;
        return;
    }
    color[u]=2;
    for(int v:vt[u]){
        if(!color[v]&&k>0){
            dfs2(v);
        }
    }
}
vector<int>task3(int n,int a,int b,int c){
    vector<pii>vv={{a,1},{b,2},{c,3}};
    sort(all(vv));
    a=vv[0].F,b=vv[1].F,c=vv[2].F;
    N=n;
    xx=a,yy=b;
    dfs(1,-1);
    if(!ok){
        vector<int>ans(n);
        return ans;
    }
    say=a;
    dfs3(res,pp,vv[0].S);
    say=b;
    dfs3(1,-1,vv[1].S);
    vector<int>ans;
    for(int i=1;i<=n;i++){
        if(color[i]){
            ans.pb(color[i]);
        }
        else{
            ans.pb(vv[2].S);
        }
    }
    return ans;
}
vector<int> task1(int n,int a,int b,int c){
    dfs(1);
    vector<int>ans;
    for(int i=0;i<a;i++){
        color[v[i]]=1;
    }
    for(int i=a;i<a+b;i++){
        color[v[i]]=2;
    }
    for(int i=a+b;i<n;i++){
        color[v[i]]=3;
    }
    for(int i=1;i<=n;i++){
        ans.pb(color[i]);
    }
    return ans;
}
vector<int> task2(int n,int a,int b,int c){
    k=b;
    dfs2(1);
    vector<int>ans;
    for(int i=1;i<=n;i++){
        if(color[i]==0&&a){
            a=0;
            color[i]=1;
        }
        else if(color[i]==0){
            color[i]=3;
        }
        ans.pb(color[i]);
    }
    return ans;
}
vector<int> find_split(int n,int a,int b,int c,vector<int>p,vector<int>q) {
	int m=p.size();
	for(int i=0;i<p.size();i++){
        d[p[i]+1]++,d[q[i]+1]++;
        vt[p[i]+1].pb(q[i]+1);
        vt[q[i]+1].pb(p[i]+1);
	}
	if(a==1){
        return task2(n,a,b,c);
	}
	if(p.size()==n-1){
        return task3(n,a,b,c);
	}
	return task1(n,a,b,c);


}

Compilation message

split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:127:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  127 |  for(int i=0;i<p.size();i++){
      |              ~^~~~~~~~~
split.cpp:135:13: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  135 |  if(p.size()==n-1){
      |     ~~~~~~~~^~~~~
split.cpp:126:6: warning: unused variable 'm' [-Wunused-variable]
  126 |  int m=p.size();
      |      ^

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB ok, correct split
2 Correct 2 ms 4948 KB ok, correct split
3 Correct 3 ms 4948 KB ok, correct split
4 Correct 3 ms 4948 KB ok, correct split
5 Correct 2 ms 4948 KB ok, correct split
6 Correct 2 ms 4948 KB ok, correct split
7 Correct 67 ms 18952 KB ok, correct split
8 Correct 55 ms 13088 KB ok, correct split
9 Correct 68 ms 15992 KB ok, correct split
10 Correct 49 ms 10888 KB ok, correct split
11 Correct 60 ms 16260 KB ok, correct split

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB ok, correct split
2 Correct 2 ms 4948 KB ok, correct split
3 Correct 2 ms 4948 KB ok, correct split
4 Correct 63 ms 12076 KB ok, correct split
5 Correct 51 ms 11148 KB ok, correct split
6 Correct 47 ms 10916 KB ok, correct split
7 Correct 53 ms 12620 KB ok, correct split
8 Correct 84 ms 13412 KB ok, correct split
9 Correct 53 ms 11088 KB ok, correct split
10 Correct 46 ms 11548 KB ok, correct split
11 Correct 48 ms 11644 KB ok, correct split
12 Correct 45 ms 11596 KB ok, correct split

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB ok, correct split
2 Incorrect 59 ms 11596 KB invalid split: #1=20000, #2=21840, #3=58160
3 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 4948 KB 2 components are not connected
2 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB ok, correct split
2 Correct 2 ms 4948 KB ok, correct split
3 Correct 3 ms 4948 KB ok, correct split
4 Correct 3 ms 4948 KB ok, correct split
5 Correct 2 ms 4948 KB ok, correct split
6 Correct 2 ms 4948 KB ok, correct split
7 Correct 67 ms 18952 KB ok, correct split
8 Correct 55 ms 13088 KB ok, correct split
9 Correct 68 ms 15992 KB ok, correct split
10 Correct 49 ms 10888 KB ok, correct split
11 Correct 60 ms 16260 KB ok, correct split
12 Correct 3 ms 4948 KB ok, correct split
13 Correct 2 ms 4948 KB ok, correct split
14 Correct 2 ms 4948 KB ok, correct split
15 Correct 63 ms 12076 KB ok, correct split
16 Correct 51 ms 11148 KB ok, correct split
17 Correct 47 ms 10916 KB ok, correct split
18 Correct 53 ms 12620 KB ok, correct split
19 Correct 84 ms 13412 KB ok, correct split
20 Correct 53 ms 11088 KB ok, correct split
21 Correct 46 ms 11548 KB ok, correct split
22 Correct 48 ms 11644 KB ok, correct split
23 Correct 45 ms 11596 KB ok, correct split
24 Correct 3 ms 4948 KB ok, correct split
25 Incorrect 59 ms 11596 KB invalid split: #1=20000, #2=21840, #3=58160
26 Halted 0 ms 0 KB -