oj.uz

Submission #275276

# Submission time Handle Problem Language Result Execution time Memory
275276 2020-08-20T05:11:22 Z khangal Split the Attractions (IOI19_split) C++14
18 / 100
 218 ms 122104 KB 
#include<bits/stdc++.h>
using namespace std;
typedef int ll;
typedef double db;
typedef pair<ll,ll> pl;
typedef vector<ll> vl;
typedef vector<vl> vvl;
#define po pop_back
#define pb push_back
#define mk make_pair
#define mt make_tuple
#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
#define read(x) scanf("%lld",&x);
#define print(x) printf("%lld ",x);
#define endl '\n';
// 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,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,res,par[1234567],cnt,sz[1234567];
bool used[1234567];
vl v[1234567],vec1;
char s1[1234567],s[1234567],ss[1234567];
vector<pl> vp[1234567];
bool ok;
map<ll,ll> mp;
ll c1[2234][2234],c2[1234][1234];
char ch[2234][2234];
ll dx[4]={0,0,1,-1},dy[4]={1,-1,0,0};
vl vec;
vector<int> vv1,vv2;
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 x){
    used[x]=1;
    vv1.pb(x);
    for(auto u:v[x]){
        if(par[u]==x)dfs1(u);
    }
}
void dfs2(int x){
    if(used[x]==1)return;
    vv2.pb(x);
    for(auto u:v[x]){
        if(par[u]==x)dfs2(u);
    }
}
vector<int> find_split(int n,int a,int b,int c, vector<int>v1,vector<int>v2){
    rep(i,0,v1.size()-1){
        v[v1[i]].pb(v2[i]);
        v[v2[i]].pb(v1[i]);
    }
    vector<int> ans(n);
    dfs(0,-1);
    vector<pair<int,int>> vv{{a,1},{b,2},{c,3}};
    sort(vv.begin(),vv.end());
    rep(i,0,n-1){
        if(sz[i]>=vv[0].ff&&n-sz[i]>=vv[1].ff){
            dfs1(i);
            dfs2(0);
            rep(j,0,vv1.size()-1){
                if(j<vv[0].ff)ans[vv1[j]]=vv[0].ss;
                else ans[vv1[j]]=vv[2].ss;
            }
            rep(j,0,vv2.size()-1){
                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);
                rep(j,0,vv1.size()-1){
                    if(j<vv[1].ff)ans[vv1[j]]=vv[1].ss;
                    else ans[vv1[j]]=vv[2].ss;
                }
                rep(j,0,vv2.size()-1){
                    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:20:32: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 | #define rep(i,a,b) for(ll i=a;i<=b;i++)
......
   65 |     rep(i,0,v1.size()-1){
      |         ~~~~~~~~~~~~~~~         
split.cpp:65:5: note: in expansion of macro 'rep'
   65 |     rep(i,0,v1.size()-1){
      |     ^~~
split.cpp:20:32: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 | #define rep(i,a,b) for(ll i=a;i<=b;i++)
......
   77 |             rep(j,0,vv1.size()-1){
      |                 ~~~~~~~~~~~~~~~~
split.cpp:77:13: note: in expansion of macro 'rep'
   77 |             rep(j,0,vv1.size()-1){
      |             ^~~
split.cpp:20:32: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 | #define rep(i,a,b) for(ll i=a;i<=b;i++)
......
   81 |             rep(j,0,vv2.size()-1){
      |                 ~~~~~~~~~~~~~~~~
split.cpp:81:13: note: in expansion of macro 'rep'
   81 |             rep(j,0,vv2.size()-1){
      |             ^~~
split.cpp:20:32: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 | #define rep(i,a,b) for(ll i=a;i<=b;i++)
......
   91 |                 rep(j,0,vv1.size()-1){
      |                     ~~~~~~~~~~~~~~~~
split.cpp:91:17: note: in expansion of macro 'rep'
   91 |                 rep(j,0,vv1.size()-1){
      |                 ^~~
split.cpp:20:32: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 | #define rep(i,a,b) for(ll i=a;i<=b;i++)
......
   95 |                 rep(j,0,vv2.size()-1){
      |                     ~~~~~~~~~~~~~~~~
split.cpp:95:17: note: in expansion of macro 'rep'
   95 |                 rep(j,0,vv2.size()-1){
      |                 ^~~
split.cpp:71:47: warning: control reaches end of non-void function [-Wreturn-type]
   71 |     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 41 ms 58360 KB ok, correct split
2 Correct 39 ms 58348 KB ok, correct split
3 Correct 43 ms 58360 KB ok, correct split
4 Correct 39 ms 58360 KB ok, correct split
5 Correct 39 ms 58368 KB ok, correct split
6 Correct 43 ms 58360 KB ok, correct split
7 Correct 159 ms 69368 KB ok, correct split
8 Correct 151 ms 68084 KB ok, correct split
9 Correct 150 ms 67736 KB ok, correct split
10 Correct 142 ms 69620 KB ok, correct split
11 Correct 141 ms 69752 KB ok, correct split

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 58360 KB ok, correct split
2 Correct 41 ms 58360 KB ok, correct split
3 Correct 39 ms 58296 KB ok, correct split
4 Correct 160 ms 68192 KB ok, correct split
5 Correct 127 ms 65016 KB ok, correct split
6 Correct 165 ms 69620 KB ok, correct split
7 Correct 180 ms 68084 KB ok, correct split
8 Correct 218 ms 67192 KB ok, correct split
9 Correct 141 ms 65016 KB ok, correct split
10 Correct 98 ms 65392 KB ok, correct split
11 Correct 99 ms 65392 KB ok, correct split
12 Correct 110 ms 65392 KB ok, correct split

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 58296 KB ok, correct split
2 Correct 135 ms 65016 KB ok, correct split
3 Correct 70 ms 61176 KB ok, correct split
4 Correct 41 ms 58360 KB ok, correct split
5 Correct 170 ms 66676 KB ok, correct split
6 Correct 160 ms 66420 KB ok, correct split
7 Correct 155 ms 66296 KB ok, correct split
8 Correct 151 ms 67188 KB ok, correct split
9 Correct 164 ms 66168 KB ok, correct split
10 Runtime error 143 ms 122104 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 44 ms 58360 KB ok, correct split
2 Runtime error 119 ms 118128 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 41 ms 58360 KB ok, correct split
2 Correct 39 ms 58348 KB ok, correct split
3 Correct 43 ms 58360 KB ok, correct split
4 Correct 39 ms 58360 KB ok, correct split
5 Correct 39 ms 58368 KB ok, correct split
6 Correct 43 ms 58360 KB ok, correct split
7 Correct 159 ms 69368 KB ok, correct split
8 Correct 151 ms 68084 KB ok, correct split
9 Correct 150 ms 67736 KB ok, correct split
10 Correct 142 ms 69620 KB ok, correct split
11 Correct 141 ms 69752 KB ok, correct split
12 Correct 39 ms 58360 KB ok, correct split
13 Correct 41 ms 58360 KB ok, correct split
14 Correct 39 ms 58296 KB ok, correct split
15 Correct 160 ms 68192 KB ok, correct split
16 Correct 127 ms 65016 KB ok, correct split
17 Correct 165 ms 69620 KB ok, correct split
18 Correct 180 ms 68084 KB ok, correct split
19 Correct 218 ms 67192 KB ok, correct split
20 Correct 141 ms 65016 KB ok, correct split
21 Correct 98 ms 65392 KB ok, correct split
22 Correct 99 ms 65392 KB ok, correct split
23 Correct 110 ms 65392 KB ok, correct split
24 Correct 42 ms 58296 KB ok, correct split
25 Correct 135 ms 65016 KB ok, correct split
26 Correct 70 ms 61176 KB ok, correct split
27 Correct 41 ms 58360 KB ok, correct split
28 Correct 170 ms 66676 KB ok, correct split
29 Correct 160 ms 66420 KB ok, correct split
30 Correct 155 ms 66296 KB ok, correct split
31 Correct 151 ms 67188 KB ok, correct split
32 Correct 164 ms 66168 KB ok, correct split
33 Runtime error 143 ms 122104 KB Execution killed with signal 11
34 Halted 0 ms 0 KB -