Submission #339286

#TimeUsernameProblemLanguageResultExecution timeMemory
33928612tqianPaths (BOI18_paths)C++17
100 / 100
893 ms36180 KiB
#pragma comment(linker, "/stack:200000000") //#pragma GCC optimize("Ofast") //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") #pragma GCC optimize ("O3") #pragma GCC target ("sse4") #include <bits/stdc++.h> #include <ext/pb_ds/tree_policy.hpp> #include <ext/pb_ds/assoc_container.hpp> using namespace std; using namespace __gnu_pbds; template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>; const double PI = 4 * atan(1); #define sz(x) (int)(x).size() #define ll long long #define ld long double #define mp make_pair #define pb push_back #define eb emplace_back #define pii pair <int, int> #define vi vector<int> #define f first #define s second #define lb lower_bound #define ub upper_bound #define all(x) x.begin(), x.end() #define vpi vector<pair<int, int>> #define vpd vector<pair<double, double>> #define pd pair<double, double> #define f0r(i,a) for(int i=0;i<a;i++) #define f1r(i,a,b) for(int i=a;i<b;i++) #define trav(a, x) for (auto& a : x) template<typename A, typename B> ostream& operator<<(ostream &cout, pair<A, B> const &p) { return cout << "(" << p.f << ", " << p.s << ")"; } template<typename A> ostream& operator<<(ostream &cout, vector<A> const &v) { cout << "["; for(int i = 0; i < v.size(); i++) {if (i) cout << ", "; cout << v[i];} return cout << "]"; } void fast_io(){ ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL); } void io(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); fast_io(); } const int MAX = 3e5 + 5; vi adj[MAX]; ll num[MAX][5]; vpi edges; int co[MAX]; ll res[6]; ll cnt[5][5]; vector<vi> states; int main(){ fast_io(); int n, m, k; cin >> n >> m >> k; f0r(i,n) cin >> co[i]; f0r(i, n) co[i]--; f0r(i, m){ int u, v; cin >> u >> v; u--; v--; adj[u].eb(v); adj[v].eb(u); edges.eb(mp(min(u, v), max(u, v))); } for(auto e: edges){ num[e.f][co[e.s]]++; num[e.s][co[e.f]]++; } if(k >= 2){ for(auto e: edges){ if(co[e.f] != co[e.s]){ res[2] += 2; } } } if(k >= 3){ f0r(i, n){ f0r(a, k){ f0r(b, k){ if(a!= b && a!= co[i] && b != co[i]){ res[3] += num[i][a]*num[i][b]; } } } } } if(k>= 4){ for(auto e: edges){ f0r(a, k){ f0r(b, k){ set<int> s; s.insert(a); s.insert(b); s.insert(co[e.f]); s.insert(co[e.s]); if(sz(s) == 4){ res[4] += 2*num[e.f][a]*num[e.s][b]; } } } } } f0r(a, 4){ f0r(b, 4){ f0r(c, 4){ f0r(d, 4){ set<int> s; s.insert(a); s.insert(b); s.insert(c); s.insert(d); if(sz(s) == 4){ vi tmp; tmp.eb(a); tmp.eb(b); tmp.eb(c); tmp.eb(d); states.eb(tmp); } } } } } if(k >= 5){ f0r(i, n){ f0r(a, 5) f0r(b, 5) cnt[a][b] = 0; for(int nxt: adj[i]){ f0r(j, 5){ cnt[co[nxt]][j] += num[nxt][j]; } } vi colors; f0r(j, 5) if(j != co[i]) colors.eb(j); for(auto v: states){ int a = colors[v[0]]; int b = colors[v[1]]; int c = colors[v[2]]; int d = colors[v[3]]; res[5] += cnt[a][b]*cnt[c][d]; } } } ll ans = 0; f1r(i, 2, k+1) ans += res[i]; cout << ans << endl; return 0; }

Compilation message (stderr)

paths.cpp:1: warning: ignoring #pragma comment  [-Wunknown-pragmas]
    1 | #pragma comment(linker, "/stack:200000000")
      | 
paths.cpp: In function 'void io(std::string)':
paths.cpp:52:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   52 |     freopen(FIN, "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~
paths.cpp:53:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   53 |     freopen(FOUT, "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...