oj.uz

Submission #473432

# Submission time Handle Problem Language Result Execution time Memory
473432 2021-09-15T13:55:49 Z Blobo2_Blobo2 Paths (BOI18_paths) C++14
23 / 100
 93 ms 31600 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[100001],n,m,k;
vector<int>adj[100001];
int vis[100001][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 7 ms 15180 KB Output is correct
2 Correct 7 ms 15180 KB Output is correct
3 Correct 7 ms 15092 KB Output is correct
4 Correct 8 ms 15180 KB Output is correct
5 Correct 8 ms 15180 KB Output is correct
6 Correct 7 ms 15180 KB Output is correct
7 Correct 8 ms 15180 KB Output is correct
8 Correct 7 ms 15180 KB Output is correct
9 Correct 8 ms 15168 KB Output is correct
10 Correct 8 ms 15180 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 21656 KB Output is correct
2 Correct 78 ms 20952 KB Output is correct
3 Runtime error 32 ms 31600 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 15180 KB Output is correct
2 Correct 7 ms 15180 KB Output is correct
3 Correct 7 ms 15092 KB Output is correct
4 Correct 8 ms 15180 KB Output is correct
5 Correct 8 ms 15180 KB Output is correct
6 Correct 7 ms 15180 KB Output is correct
7 Correct 8 ms 15180 KB Output is correct
8 Correct 7 ms 15180 KB Output is correct
9 Correct 8 ms 15168 KB Output is correct
10 Correct 8 ms 15180 KB Output is correct
11 Correct 93 ms 21656 KB Output is correct
12 Correct 78 ms 20952 KB Output is correct
13 Runtime error 32 ms 31600 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 15180 KB Output is correct
2 Incorrect 47 ms 17048 KB Output isn't correct
3 Halted 0 ms 0 KB -