oj.uz

Submission #658877

# Submission time Handle Problem Language Result Execution time Memory
658877 2022-11-15T09:56:10 Z Soul234 Paths (BOI18_paths) C++14
100 / 100
 454 ms 97228 KB 
#include<bits/stdc++.h>
using namespace std;

void DBG() { cerr << "]\n"; }
template<class H, class... T> void DBG(H h, T... t) {
    cerr << h; if(sizeof...(t)) cerr << ", ";
    DBG(t...);
}
#ifdef LOCAL
#define dbg(...) cerr << "[" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__)
#else
#define dbg(...) 0
#endif // LOCAL

#define FOR(i,a,b) for(int i = (a) ; i<(b) ; i++)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for(int i = (b)-1 ; i>=(a) ; i--)
#define R0F(i,a) ROF(i,0,a)
#define each(e,a) for(auto &e : (a))
#define sz(v) (int)(v).size()
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define pb push_back
#define tcT template<class T
#define nl "\n"
#define fi first
#define se second

using ll = long long;
using vi = vector<int>;
using pi = pair<int,int>;
using str = string;
using db = long double;
tcT> using V = vector<T>;
tcT> using pqg = priority_queue<T,vector<T>,greater<T>>;

void setIO(string NAME = "") {
    cin.tie(0)->sync_with_stdio(0);
    if(sz(NAME)) {
        freopen((NAME + ".inp").c_str(),"r",stdin);
        freopen((NAME + ".out").c_str(),"w",stdout);
    }
}

tcT> bool ckmin(T&a, const T&b) {
    return b < a ? a=b,1 : 0; }
tcT> bool ckmax(T&a, const T&b) {
    return b > a ? a=b,1 : 0; }

const int MOD = 1e9 + 7;
const ll INF = 1e18;

const int MX = 3e5+5;

int N, M, K;

ll dp[MX][1<<5], ans;

int col[MX];

vi adj[MX];

void dfs(int u, int msk) {
    if(~dp[u][msk]) return;
    if(msk>>col[u]&1) {
        dp[u][msk] = 0;
        return;
    }
    dp[u][msk] = 1;
    int nmsk = msk | (1<<col[u]);
    each(v, adj[u]) {
        dfs(v, nmsk);
        dp[u][msk] += dp[v][nmsk];
    }
}

void solve() {
    cin >> N >> M >> K;
    memset(dp, -1, sizeof dp);
    FOR(i,1,N+1) cin >> col[i], col[i]--;
    F0R(i, M) {
        int u, v;
        cin >> u >> v;
        adj[u].pb(v);
        adj[v].pb(u);
    }
    FOR(i,1,N+1) {
        dfs(i, 0);
        ans += dp[i][0];
    }
    cout << ans - N << nl;
}

int main() {
    setIO();

    int t=1;
    //cin>>t;
    while(t-->0) {
        solve();
    }

    return 0;
}

Compilation message

paths.cpp: In function 'void setIO(std::string)':
paths.cpp:40:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |         freopen((NAME + ".inp").c_str(),"r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
paths.cpp:41:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |         freopen((NAME + ".out").c_str(),"w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 82516 KB Output is correct
2 Correct 33 ms 82380 KB Output is correct
3 Correct 35 ms 82488 KB Output is correct
4 Correct 41 ms 82508 KB Output is correct
5 Correct 35 ms 82432 KB Output is correct
6 Correct 34 ms 82516 KB Output is correct
7 Correct 42 ms 82508 KB Output is correct
8 Correct 33 ms 82396 KB Output is correct
9 Correct 45 ms 82396 KB Output is correct
10 Correct 34 ms 82384 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 88892 KB Output is correct
2 Correct 89 ms 88364 KB Output is correct
3 Correct 338 ms 96512 KB Output is correct
4 Correct 141 ms 90464 KB Output is correct
5 Correct 124 ms 90376 KB Output is correct
6 Correct 280 ms 94396 KB Output is correct
7 Correct 372 ms 96508 KB Output is correct
8 Correct 320 ms 97168 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 82516 KB Output is correct
2 Correct 33 ms 82380 KB Output is correct
3 Correct 35 ms 82488 KB Output is correct
4 Correct 41 ms 82508 KB Output is correct
5 Correct 35 ms 82432 KB Output is correct
6 Correct 34 ms 82516 KB Output is correct
7 Correct 42 ms 82508 KB Output is correct
8 Correct 33 ms 82396 KB Output is correct
9 Correct 45 ms 82396 KB Output is correct
10 Correct 34 ms 82384 KB Output is correct
11 Correct 90 ms 88892 KB Output is correct
12 Correct 89 ms 88364 KB Output is correct
13 Correct 338 ms 96512 KB Output is correct
14 Correct 141 ms 90464 KB Output is correct
15 Correct 124 ms 90376 KB Output is correct
16 Correct 280 ms 94396 KB Output is correct
17 Correct 372 ms 96508 KB Output is correct
18 Correct 320 ms 97168 KB Output is correct
19 Correct 108 ms 88908 KB Output is correct
20 Correct 83 ms 88268 KB Output is correct
21 Correct 348 ms 96604 KB Output is correct
22 Correct 120 ms 90368 KB Output is correct
23 Correct 140 ms 90308 KB Output is correct
24 Correct 238 ms 94400 KB Output is correct
25 Correct 367 ms 96604 KB Output is correct
26 Correct 305 ms 97228 KB Output is correct
27 Correct 87 ms 88336 KB Output is correct
28 Correct 111 ms 89796 KB Output is correct
29 Correct 411 ms 96464 KB Output is correct
30 Correct 370 ms 93004 KB Output is correct
31 Correct 309 ms 92880 KB Output is correct
32 Correct 454 ms 96496 KB Output is correct
33 Correct 36 ms 82440 KB Output is correct
34 Correct 35 ms 82400 KB Output is correct
35 Correct 35 ms 82412 KB Output is correct
36 Correct 35 ms 82448 KB Output is correct
37 Correct 35 ms 82384 KB Output is correct
38 Correct 37 ms 82380 KB Output is correct
39 Correct 39 ms 82388 KB Output is correct
40 Correct 35 ms 82476 KB Output is correct
41 Correct 36 ms 82436 KB Output is correct
42 Correct 35 ms 82380 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 82380 KB Output is correct
2 Correct 56 ms 84240 KB Output is correct
3 Correct 52 ms 84340 KB Output is correct
4 Correct 117 ms 86996 KB Output is correct
5 Correct 79 ms 87760 KB Output is correct
6 Correct 162 ms 86976 KB Output is correct
7 Correct 54 ms 84428 KB Output is correct
8 Correct 140 ms 86920 KB Output is correct
9 Correct 79 ms 87764 KB Output is correct
10 Correct 98 ms 87764 KB Output is correct
11 Correct 118 ms 85584 KB Output is correct
12 Correct 97 ms 86856 KB Output is correct
13 Correct 108 ms 85836 KB Output is correct
14 Correct 150 ms 86996 KB Output is correct
15 Correct 123 ms 87112 KB Output is correct
16 Correct 38 ms 82504 KB Output is correct
17 Correct 36 ms 82416 KB Output is correct
18 Correct 33 ms 82472 KB Output is correct
19 Correct 35 ms 82488 KB Output is correct
20 Correct 37 ms 82508 KB Output is correct
21 Correct 35 ms 82520 KB Output is correct
22 Correct 35 ms 82504 KB Output is correct
23 Correct 34 ms 82508 KB Output is correct
24 Correct 42 ms 82432 KB Output is correct
25 Correct 36 ms 82408 KB Output is correct