oj.uz

Submission #473433

# Submission time Handle Problem Language Result Execution time Memory
473433 2021-09-15T13:56:22 Z Blobo2_Blobo2 Paths (BOI18_paths) C++14
23 / 100
 363 ms 58460 KB 
/*
Editor: Abdelrahman Hossam
Nickname: Blobo2_Blobo2
IOI next year isA :)
*/
/*#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.2,popcnt,abm,mmx,avx2,tune=native")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-funroll-all-loops,-fpeel-loops,-funswitch-loops")*/

#include<bits/stdc++.h>
using namespace std;
//#define int long long
#define endl "\n"
#define all(v)  v.begin(),v.end()
#define gen(arr,n,nxt)  generate(arr,arr+n,nxt)
#define Blobo2_el_7akim_elly_3ayz_yro7_IOI_w_3ayz_yakol_jilaty ios_base::sync_with_stdio(false);cin.tie(0);
#define EPS 0.00000001

const int mo=1e9+7,INF=1e18;
int nxt(){int x;cin>>x;return x;}
int color[300001],n,m,k;
vector<int>adj[300001];
int vis[300001][32];
int dfs(int u, int c){
    int &ret = vis[u][c];
    if(ret!=-1)return ret;
    int cnt = __builtin_popcount(c) != 1;
    for(auto v:adj[u]){
        if(!(c&color[v]))
            cnt += dfs(v,c+color[v]);
    }
    return ret=cnt;
}
signed main(){
    Blobo2_el_7akim_elly_3ayz_yro7_IOI_w_3ayz_yakol_jilaty
    //freopen("in.txt","r",stdin);
    n=nxt(),m=nxt(),k=nxt();
    memset(vis,-1,sizeof vis);
    for(int i=0;i<n;i++){
        int x = nxt();
        if(x == 3)x=4;
        else if(x == 4)x=8;
        else if(x == 5)x=16;
        color[i] = x;
    }
    for(int i=0;i<m;i++){
        int x= nxt()-1,y=nxt()-1;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    int cnt=0;
    for(int i=0;i<n;i++){
        int ans = dfs(i,color[i]);
        cnt+=ans;
    }
    cout<<cnt;
    return 0;
}

Compilation message

paths.cpp:21:24: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   21 | const int mo=1e9+7,INF=1e18;
      |                        ^~~~

Subtask #1
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 44820 KB Output is correct
2 Correct 21 ms 44892 KB Output is correct
3 Correct 20 ms 44940 KB Output is correct
4 Correct 20 ms 44908 KB Output is correct
5 Correct 21 ms 44924 KB Output is correct
6 Correct 22 ms 44876 KB Output is correct
7 Correct 20 ms 44880 KB Output is correct
8 Correct 21 ms 44880 KB Output is correct
9 Correct 22 ms 44876 KB Output is correct
10 Correct 20 ms 44892 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 48580 KB Output is correct
2 Correct 90 ms 48416 KB Output is correct
3 Correct 363 ms 58460 KB Output is correct
4 Correct 153 ms 52812 KB Output is correct
5 Correct 133 ms 52792 KB Output is correct
6 Incorrect 258 ms 56840 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 44820 KB Output is correct
2 Correct 21 ms 44892 KB Output is correct
3 Correct 20 ms 44940 KB Output is correct
4 Correct 20 ms 44908 KB Output is correct
5 Correct 21 ms 44924 KB Output is correct
6 Correct 22 ms 44876 KB Output is correct
7 Correct 20 ms 44880 KB Output is correct
8 Correct 21 ms 44880 KB Output is correct
9 Correct 22 ms 44876 KB Output is correct
10 Correct 20 ms 44892 KB Output is correct
11 Correct 104 ms 48580 KB Output is correct
12 Correct 90 ms 48416 KB Output is correct
13 Correct 363 ms 58460 KB Output is correct
14 Correct 153 ms 52812 KB Output is correct
15 Correct 133 ms 52792 KB Output is correct
16 Incorrect 258 ms 56840 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 44940 KB Output is correct
2 Incorrect 58 ms 46004 KB Output isn't correct
3 Halted 0 ms 0 KB -