oj.uz

Submission #887657

# Submission time Handle Problem Language Result Execution time Memory
887657 2023-12-15T00:58:41 Z nnhzzz Paths (BOI18_paths) C++14
23 / 100
 172 ms 54612 KB 
#include<bits/stdc++.h>

using namespace std;

#define REP(i,a,b) for(int i = (a); i<=(b); ++i)
#define REPD(i,a,b) for(int i = (a); i>=(b); --i)
#define REPDIS(i,a,b,c) for(int i = (a); i<=(b); i += c)
#define ALL(x) (x).begin(),(x).end()
#define SZ(x) (int)(x).size()
#define MASK(x) (1LL<<(x))
#define BIT(x,i) (((x)>>(i))&1LL)
#define vi vector<int>
#define vvi vector<vi>
#define vvvi vector<vvi>
#define pii pair<int,int>
#define vpii vector<pii>
#define vvpii vector<vpii>
#define fi first
#define se second
#define gcd __gcd
#define ld long double
#define ll long long
#define ull unsigned long long
#define MP make_pair
#define endl "\n"
// #define int ll

//-------------------------------------------------------------------------------------------------------//
int readInt(){
    char c;
    do{
        c = getchar();
    }while(c!='-' && !isdigit(c));
    bool neg = (c=='-');
    int res = neg?0:c-'0';
    while(isdigit(c=getchar())) res = (res<<3)+(res<<1)+(c-'0');
    return neg?-res:res;
}
//-------------------------------------------------------------------------------------------------------//
template<typename T> bool mini(T &a, const T &b){if(a>b){a=b;return true;}return false;}
template<typename T> bool maxi(T &a, const T &b){if(a<b){a=b;return true;}return false;}
//-------------------------------------------------------------------------------------------------------//
const int MAXN = 3e5+7;
const int MOD = 1e9+7;
const int INF = 1e9;
const int LOG = 16;
const ll LINF = 5e17;
const ld EPS = 1e-9;
const ld PI = acos(-1);
//-------------------------------------------------------------------------------------------------------//

int dp[MAXN][MASK(5)],a[MAXN];
vi adj[MAXN];
int n,m,k,res = 0;

void solve(){
    cin >> n >> m >> k;
    REP(i,0,n-1){
        cin >> a[i];
        --a[i];
        dp[i][MASK(a[i])] = 1;;
    }
    REP(i,1,m){
        int u,v; cin >> u >> v;
        --u; --v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    REP(state,0,MASK(k)-1){
        REP(u,0,n-1){
            if(dp[u][state]==0) continue;
            res += dp[u][state];
            for(int &v:adj[u]){
                if(state&(MASK(a[v]))) continue;
                dp[v][state|MASK(a[v])] += dp[u][state];
            }
        }
    }
    cout << res-n;
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    #define task "test"
    if(fopen(task".inp","r")){
        freopen(task".inp","r",stdin);
        freopen(task".out","w",stdout);
    }
    #define task1 "nothing"
    if(fopen(task1".inp","r")){
        freopen(task1".inp","r",stdin);
        freopen(task1".out","w",stdout);
    }
    int test = 1;
    while(test--) solve();
    return 0;
}

Compilation message

paths.cpp: In function 'int main()':
paths.cpp:88:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   88 |         freopen(task".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
paths.cpp:89:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   89 |         freopen(task".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
paths.cpp:93:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   93 |         freopen(task1".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
paths.cpp:94:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   94 |         freopen(task1".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8796 KB Output is correct
2 Correct 2 ms 8796 KB Output is correct
3 Correct 2 ms 8948 KB Output is correct
4 Correct 2 ms 8796 KB Output is correct
5 Correct 2 ms 8796 KB Output is correct
6 Correct 2 ms 8796 KB Output is correct
7 Correct 2 ms 8796 KB Output is correct
8 Correct 2 ms 8796 KB Output is correct
9 Correct 2 ms 8792 KB Output is correct
10 Correct 2 ms 8796 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 14420 KB Output is correct
2 Correct 40 ms 12372 KB Output is correct
3 Correct 172 ms 54612 KB Output is correct
4 Correct 61 ms 17168 KB Output is correct
5 Correct 73 ms 17180 KB Output is correct
6 Incorrect 116 ms 42436 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8796 KB Output is correct
2 Correct 2 ms 8796 KB Output is correct
3 Correct 2 ms 8948 KB Output is correct
4 Correct 2 ms 8796 KB Output is correct
5 Correct 2 ms 8796 KB Output is correct
6 Correct 2 ms 8796 KB Output is correct
7 Correct 2 ms 8796 KB Output is correct
8 Correct 2 ms 8796 KB Output is correct
9 Correct 2 ms 8792 KB Output is correct
10 Correct 2 ms 8796 KB Output is correct
11 Correct 50 ms 14420 KB Output is correct
12 Correct 40 ms 12372 KB Output is correct
13 Correct 172 ms 54612 KB Output is correct
14 Correct 61 ms 17168 KB Output is correct
15 Correct 73 ms 17180 KB Output is correct
16 Incorrect 116 ms 42436 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8796 KB Output is correct
2 Incorrect 25 ms 9964 KB Output isn't correct
3 Halted 0 ms 0 KB -