oj.uz

Submission #500936

# Submission time Handle Problem Language Result Execution time Memory
500936 2022-01-01T17:26:20 Z Khizri Split the Attractions (IOI19_split) C++17
18 / 100
 86 ms 16324 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;
vector<int>vt[mxn];
vector<int>v;
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> 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);
	}
	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:75:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |  for(int i=0;i<p.size();i++){
      |              ~^~~~~~~~~
split.cpp:74:6: warning: unused variable 'm' [-Wunused-variable]
   74 |  int m=p.size();
      |      ^

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB ok, correct split
2 Correct 2 ms 4940 KB ok, correct split
3 Correct 2 ms 4940 KB ok, correct split
4 Correct 3 ms 4948 KB ok, correct split
5 Correct 2 ms 4940 KB ok, correct split
6 Correct 3 ms 4940 KB ok, correct split
7 Correct 80 ms 16008 KB ok, correct split
8 Correct 63 ms 13164 KB ok, correct split
9 Correct 58 ms 14236 KB ok, correct split
10 Correct 53 ms 11040 KB ok, correct split
11 Correct 86 ms 16324 KB ok, correct split

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4940 KB ok, correct split
2 Correct 2 ms 4940 KB ok, correct split
3 Correct 3 ms 4940 KB ok, correct split
4 Correct 66 ms 12068 KB ok, correct split
5 Correct 70 ms 11136 KB ok, correct split
6 Correct 53 ms 12048 KB ok, correct split
7 Correct 64 ms 13828 KB ok, correct split
8 Correct 84 ms 15568 KB ok, correct split
9 Correct 65 ms 12304 KB ok, correct split
10 Correct 45 ms 12308 KB ok, correct split
11 Correct 42 ms 12292 KB ok, correct split
12 Correct 45 ms 12756 KB ok, correct split

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4940 KB ok, correct split
2 Incorrect 57 ms 11720 KB 2 components are not connected
3 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 4940 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 4940 KB ok, correct split
2 Correct 2 ms 4940 KB ok, correct split
3 Correct 2 ms 4940 KB ok, correct split
4 Correct 3 ms 4948 KB ok, correct split
5 Correct 2 ms 4940 KB ok, correct split
6 Correct 3 ms 4940 KB ok, correct split
7 Correct 80 ms 16008 KB ok, correct split
8 Correct 63 ms 13164 KB ok, correct split
9 Correct 58 ms 14236 KB ok, correct split
10 Correct 53 ms 11040 KB ok, correct split
11 Correct 86 ms 16324 KB ok, correct split
12 Correct 2 ms 4940 KB ok, correct split
13 Correct 2 ms 4940 KB ok, correct split
14 Correct 3 ms 4940 KB ok, correct split
15 Correct 66 ms 12068 KB ok, correct split
16 Correct 70 ms 11136 KB ok, correct split
17 Correct 53 ms 12048 KB ok, correct split
18 Correct 64 ms 13828 KB ok, correct split
19 Correct 84 ms 15568 KB ok, correct split
20 Correct 65 ms 12304 KB ok, correct split
21 Correct 45 ms 12308 KB ok, correct split
22 Correct 42 ms 12292 KB ok, correct split
23 Correct 45 ms 12756 KB ok, correct split
24 Correct 2 ms 4940 KB ok, correct split
25 Incorrect 57 ms 11720 KB 2 components are not connected
26 Halted 0 ms 0 KB -