oj.uz

Submission #275382

# Submission time Handle Problem Language Result Execution time Memory
275382 2020-08-20T05:47:00 Z khangal Split the Attractions (IOI19_split) C++14
18 / 100
 172 ms 63092 KB 
#include<bits/stdc++.h>
using namespace std;
typedef int ll;
typedef pair<ll,ll> pl;
typedef vector<ll> vl;
#define po pop_back
#define pb push_back
#define mk make_pair
#define lw lower_bound
#define up upper_bound
#define ff first
#define ss second
#define boost ios_base::sync_with_stdio(); cin.tie(0); cout.tie(0);
#define MOD 1000000007
#define MAX 1e18
#define MIN -1e18
#define rep(i,a,b) for(ll i=a;i<=b;i++)
#define per(i,a,b) for(ll i=b;i>=a;i--)
#define con continue
#define freopen freopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout);
#define PI 3.14159265358979323846264338327950288419716939937510582097494459230781640628
// typedef tree<ll , null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
// template< typename T>
// using indexed_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
ll n,m,ans,mid,mn,mx,cnt,T,sum,h1,h2,e[1234567],b[1234567],c[1234567],d[1<<20],k,i,j,l,r,h,a[1234567],w,x,y,z;
bool used[1234567];
vector<int> v[1234567],vec,vv1,vv2;
string s1,s;
int sz[1234567],par[1234567];
ll dx[4]={-1,1,0,0},dy[4]={0,0,-1,1},c1[123][123];
int dfs(int node , int p){
    if(sz[node] > 0) return 0;
    par[node] = p;
    sz[node] = 1;
    for(auto x : v[node]) sz[node] += dfs(x , node);
    return sz[node];
}
void dfs1(int node){
    used[node] = 1;
    vv1.pb(node);
    for(auto x : v[node]) if(par[x] == node) dfs1(x);
    return;
}
void dfs2(int node){
    if(used[node]) return;
    vv2.pb(node);
    for(auto x : v[node]) if(par[x] == node) dfs2(x);
    return;
}
vector<int> find_split(int n ,  int  a , int b ,int c  ,vector<int>v1 , vector<int>v2){
    int m = v1.size();
    for(int i=0; i<m; i++){
        v[v2[i]].pb(v1[i]);
        v[v1[i]].pb(v2[i]);
    }
    dfs(0,-1);
    vector<pair<int , int>> vv = {{a, 1}, {b, 2}, {c, 3}};
    sort(vv.begin(), vv.end());
    vector<int> ans(n, 0);
    for(int i=0; i<n; i++){
        if(sz[i] >= vv[0].ff && n-sz[i] >= vv[1].ff){
            dfs1(i);
            dfs2(0);
            for(int j=0; j<vv1.size(); j++){
                if(j < vv[0].ff) ans[vv1[j]] = vv[0].ss;
                else ans[vv1[j]] = vv[2].ss;
            }
            for(int j=0; j<vv2.size(); j++){
                if(j < vv[1].ff) ans[vv2[j]] = vv[1].ss;
                else ans[vv2[j]] = vv[2].ss;
            }
            return ans;
        } 
        else 
            if(sz[i] >= vv[1].ff && n-sz[i] >= vv[0].ff){
                dfs1(i);
                dfs2(0);
                for(int j=0; j<vv1.size(); j++){
                    if(j < vv[1].ff) ans[vv1[j]] = vv[1].ss;
                    else ans[vv1[j]] = vv[2].ss;
                }
                for(int j=0; j<vv2.size(); j++){
                    if(j < vv[0].ff) ans[vv2[j]] = vv[0].ss;
                    else ans[vv2[j]] = vv[2].ss;
            }
            return ans;
            }
    }
}

Compilation message

split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:64:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |             for(int j=0; j<vv1.size(); j++){
      |                          ~^~~~~~~~~~~
split.cpp:68:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |             for(int j=0; j<vv2.size(); j++){
      |                          ~^~~~~~~~~~~
split.cpp:78:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |                 for(int j=0; j<vv1.size(); j++){
      |                              ~^~~~~~~~~~~
split.cpp:82:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |                 for(int j=0; j<vv2.size(); j++){
      |                              ~^~~~~~~~~~~
split.cpp:57:57: warning: control reaches end of non-void function [-Wreturn-type]
   57 |     vector<pair<int , int>> vv = {{a, 1}, {b, 2}, {c, 3}};
      |                                                         ^

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 29304 KB ok, correct split
2 Correct 21 ms 29312 KB ok, correct split
3 Correct 21 ms 29312 KB ok, correct split
4 Correct 23 ms 29312 KB ok, correct split
5 Correct 22 ms 29384 KB ok, correct split
6 Correct 23 ms 29312 KB ok, correct split
7 Correct 144 ms 40440 KB ok, correct split
8 Correct 160 ms 39156 KB ok, correct split
9 Correct 144 ms 38832 KB ok, correct split
10 Correct 159 ms 40820 KB ok, correct split
11 Correct 134 ms 40568 KB ok, correct split

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 29312 KB ok, correct split
2 Correct 20 ms 29312 KB ok, correct split
3 Correct 20 ms 29312 KB ok, correct split
4 Correct 154 ms 39284 KB ok, correct split
5 Correct 113 ms 35960 KB ok, correct split
6 Correct 136 ms 40692 KB ok, correct split
7 Correct 122 ms 39080 KB ok, correct split
8 Correct 172 ms 38264 KB ok, correct split
9 Correct 113 ms 36156 KB ok, correct split
10 Correct 77 ms 36336 KB ok, correct split
11 Correct 84 ms 36464 KB ok, correct split
12 Correct 79 ms 36464 KB ok, correct split

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 29312 KB ok, correct split
2 Correct 102 ms 36076 KB ok, correct split
3 Correct 48 ms 32120 KB ok, correct split
4 Correct 21 ms 29312 KB ok, correct split
5 Correct 125 ms 37684 KB ok, correct split
6 Correct 150 ms 37492 KB ok, correct split
7 Correct 118 ms 37240 KB ok, correct split
8 Correct 116 ms 38220 KB ok, correct split
9 Correct 118 ms 37112 KB ok, correct split
10 Runtime error 78 ms 63092 KB Execution killed with signal 11
11 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 29312 KB ok, correct split
2 Runtime error 59 ms 59200 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 29304 KB ok, correct split
2 Correct 21 ms 29312 KB ok, correct split
3 Correct 21 ms 29312 KB ok, correct split
4 Correct 23 ms 29312 KB ok, correct split
5 Correct 22 ms 29384 KB ok, correct split
6 Correct 23 ms 29312 KB ok, correct split
7 Correct 144 ms 40440 KB ok, correct split
8 Correct 160 ms 39156 KB ok, correct split
9 Correct 144 ms 38832 KB ok, correct split
10 Correct 159 ms 40820 KB ok, correct split
11 Correct 134 ms 40568 KB ok, correct split
12 Correct 23 ms 29312 KB ok, correct split
13 Correct 20 ms 29312 KB ok, correct split
14 Correct 20 ms 29312 KB ok, correct split
15 Correct 154 ms 39284 KB ok, correct split
16 Correct 113 ms 35960 KB ok, correct split
17 Correct 136 ms 40692 KB ok, correct split
18 Correct 122 ms 39080 KB ok, correct split
19 Correct 172 ms 38264 KB ok, correct split
20 Correct 113 ms 36156 KB ok, correct split
21 Correct 77 ms 36336 KB ok, correct split
22 Correct 84 ms 36464 KB ok, correct split
23 Correct 79 ms 36464 KB ok, correct split
24 Correct 20 ms 29312 KB ok, correct split
25 Correct 102 ms 36076 KB ok, correct split
26 Correct 48 ms 32120 KB ok, correct split
27 Correct 21 ms 29312 KB ok, correct split
28 Correct 125 ms 37684 KB ok, correct split
29 Correct 150 ms 37492 KB ok, correct split
30 Correct 118 ms 37240 KB ok, correct split
31 Correct 116 ms 38220 KB ok, correct split
32 Correct 118 ms 37112 KB ok, correct split
33 Runtime error 78 ms 63092 KB Execution killed with signal 11
34 Halted 0 ms 0 KB -