oj.uz

Submission #468069

# Submission time Handle Problem Language Result Execution time Memory
468069 2021-08-26T11:35:36 Z Carmel_Ab1 Paths (BOI18_paths) C++17
100 / 100
 813 ms 108936 KB 
#include<bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>

//using namespace __gnu_pbds;
using namespace std;

typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef vector<pl> vpl;
typedef vector<ld> vld;
typedef pair<ld, ld> pld;

//typedef tree<ll, null_type, less_equal<ll>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
template<typename T>
ostream &operator<<(ostream &os, vector<T> &a) {
    os << "[";
    for (int i = 0; i < ll(a.size()); i++) { os << a[i] << ((i != ll(a.size() - 1) ? " " : "")); }
    os << "]\n";
    return os;
}

#define all(x) x.begin(),x.end()
#define YES out("YES")
#define NO out("NO")
#define out(x){cout << x << "\n"; return;}
#define GLHF ios_base::sync_with_stdio(false); cin.tie(NULL)
#define print(x){for(auto ait:x) cout << ait << " "; cout << "\n";}
#define pb push_back
#define umap unordered_map

template<typename T1, typename T2>
istream &operator>>(istream &is, pair<T1, T2> &p) {
    is >> p.first >> p.second;
    return is;
}

template<typename T1, typename T2>
ostream &operator<<(ostream &os, pair<T1, T2> &p) {
    os << "" << p.first << " " << p.second << "";
    return os;
}

void usaco(string taskname) {
    string fin = taskname + ".in";
    string fout = taskname + ".out";
    const char *FIN = fin.c_str();
    const char *FOUT = fout.c_str();
    freopen(FIN, "r", stdin);
    freopen(FOUT, "w", stdout);
}

template<typename T>
void read(vector<T> &v) {
    int n = v.size();
    for (int i = 0; i < n; i++)
        cin >> v[i];
}

template<typename T>
vector<T> UNQ(vector<T> a) {
    vector<T> ans;
    for (T t:a)
        if (ans.empty() || t != ans.back())
            ans.push_back(t);
    return ans;
}

ll ceil(ll a, ll b) {
    ll ans = a / b;
    if (a % b)ans++;
    return ans;
}

ld log(ld a, ld b) { return log(b) / log(a); }

ll power(ll base, ll exp, ll M = 1e18) {//(base^exp)%M
    ll ans = 1;
    while (exp) {
        if (exp % 2 == 1)ans = ((ans % M) * (base % M)) % M;
        base = ((base % M) * (base % M)) % M;
        exp /= 2;
    }
    return ans;
}

string to_base(int n, int new_base) {
    string s;
    int nn = n;
    while (nn) {
        s += to_string(nn % new_base);
        nn /= new_base;
    }
    reverse(all(s));
    return s;
}

ll gcd(ll a, ll b) {
    if (a < b)swap(a, b);
    if (b == 0)return a;
    return gcd(b, a % b);
}

ll lcm(ll a, ll b) {
    ll x = (a / gcd(a, b));
    return b * x;
}

vl generate_array(ll n, ll mn = 1, ll mx = 1e18 + 1) {
    if (mx == 1e18 + 1)
        mx = n;
    vl ans(n);
    for (int i = 0; i < n; i++)
        ans[i] = (mn + rand() % (mx - mn + 1));
    return ans;
}

string substr(string s, int l, int r) {
    string ans;
    for (int i = l; i <= r; i++)
        ans += s[i];
    return ans;
}


void solve();

int main() {
    GLHF;
    int t = 1;
    //cin >> t;
    while (t--)
        solve();
}
int n,m,k;
vvi g;
vvl dp;
vi a;
void solve() {
    cin >> n >> m >> k;
    a.resize(n+1);
    for(int i=1; i<=n; i++) {
        cin >> a[i];
        a[i]--;
    }
    g.resize(n+1);
    for(int i=0; i<m; i++){
        int u,v;
        cin >> u >> v;
        g[u].pb(v);
        g[v].pb(u);
    }

    dp.resize(n+1,vl(1<<5));
    for(int i=1; i<=n; i++)
        dp[i][1<<a[i]]=1;
    vi ord;
    for(int i=0; i<(1<<5); i++)
        if(__builtin_popcount(i)>1)
            ord.pb(i);
    sort(all(ord),[](int x,int y){
        return __builtin_popcount(x)< __builtin_popcount(y);
    });

    for(int j=0; j<ord.size(); j++){
        int msk=ord[j];
        for(int i=1; i<=n; i++){
            if(!(msk&(1<<a[i])))
                continue;
            for(int nbr:g[i])
                dp[i][msk]+=dp[nbr][msk-(1<<a[i])];
        }
    }
    ll ans=0;
    for(int i=1; i<=n; i++)
        for(int j=0; j<dp[i].size(); j++)
            ans+=dp[i][j];
    ans-=n;
    out(ans)
}

Compilation message

paths.cpp: In function 'void solve()':
paths.cpp:172:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  172 |     for(int j=0; j<ord.size(); j++){
      |                  ~^~~~~~~~~~~
paths.cpp:183:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  183 |         for(int j=0; j<dp[i].size(); j++)
      |                      ~^~~~~~~~~~~~~
paths.cpp: In function 'void usaco(std::string)':
paths.cpp:56:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   56 |     freopen(FIN, "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~
paths.cpp:57:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |     freopen(FOUT, "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Correct 1 ms 312 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 7996 KB Output is correct
2 Correct 73 ms 6212 KB Output is correct
3 Correct 789 ms 108360 KB Output is correct
4 Correct 215 ms 17560 KB Output is correct
5 Correct 207 ms 17560 KB Output is correct
6 Correct 552 ms 74976 KB Output is correct
7 Correct 807 ms 108264 KB Output is correct
8 Correct 813 ms 108924 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Correct 1 ms 312 KB Output is correct
11 Correct 100 ms 7996 KB Output is correct
12 Correct 73 ms 6212 KB Output is correct
13 Correct 789 ms 108360 KB Output is correct
14 Correct 215 ms 17560 KB Output is correct
15 Correct 207 ms 17560 KB Output is correct
16 Correct 552 ms 74976 KB Output is correct
17 Correct 807 ms 108264 KB Output is correct
18 Correct 813 ms 108924 KB Output is correct
19 Correct 95 ms 7992 KB Output is correct
20 Correct 72 ms 6152 KB Output is correct
21 Correct 797 ms 108292 KB Output is correct
22 Correct 201 ms 17604 KB Output is correct
23 Correct 195 ms 17572 KB Output is correct
24 Correct 551 ms 74916 KB Output is correct
25 Correct 794 ms 108268 KB Output is correct
26 Correct 811 ms 108936 KB Output is correct
27 Correct 74 ms 6204 KB Output is correct
28 Correct 122 ms 9804 KB Output is correct
29 Correct 792 ms 108324 KB Output is correct
30 Correct 474 ms 57736 KB Output is correct
31 Correct 486 ms 57804 KB Output is correct
32 Correct 786 ms 108304 KB Output is correct
33 Correct 1 ms 204 KB Output is correct
34 Correct 1 ms 332 KB Output is correct
35 Correct 1 ms 332 KB Output is correct
36 Correct 1 ms 332 KB Output is correct
37 Correct 1 ms 332 KB Output is correct
38 Correct 1 ms 332 KB Output is correct
39 Correct 1 ms 332 KB Output is correct
40 Correct 1 ms 332 KB Output is correct
41 Correct 1 ms 204 KB Output is correct
42 Correct 1 ms 204 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 25 ms 2088 KB Output is correct
3 Correct 25 ms 2120 KB Output is correct
4 Correct 201 ms 36088 KB Output is correct
5 Correct 138 ms 36796 KB Output is correct
6 Correct 216 ms 36224 KB Output is correct
7 Correct 25 ms 2124 KB Output is correct
8 Correct 219 ms 36152 KB Output is correct
9 Correct 135 ms 36796 KB Output is correct
10 Correct 192 ms 36672 KB Output is correct
11 Correct 106 ms 19040 KB Output is correct
12 Correct 113 ms 28092 KB Output is correct
13 Correct 105 ms 19220 KB Output is correct
14 Correct 209 ms 36184 KB Output is correct
15 Correct 209 ms 36164 KB Output is correct
16 Correct 0 ms 204 KB Output is correct
17 Correct 1 ms 332 KB Output is correct
18 Correct 1 ms 332 KB Output is correct
19 Correct 1 ms 332 KB Output is correct
20 Correct 1 ms 332 KB Output is correct
21 Correct 1 ms 332 KB Output is correct
22 Correct 1 ms 332 KB Output is correct
23 Correct 1 ms 332 KB Output is correct
24 Correct 0 ms 204 KB Output is correct
25 Correct 1 ms 204 KB Output is correct