結果
問題 | No.2588 Increasing Record |
ユーザー | chineristAC |
提出日時 | 2023-12-16 00:59:56 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 453 ms / 3,000 ms |
コード長 | 3,854 bytes |
コンパイル時間 | 3,846 ms |
コンパイル使用メモリ | 203,956 KB |
実行使用メモリ | 68,768 KB |
最終ジャッジ日時 | 2023-12-16 01:00:25 |
合計ジャッジ時間 | 17,441 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,676 KB |
testcase_01 | AC | 2 ms
6,676 KB |
testcase_02 | AC | 2 ms
6,676 KB |
testcase_03 | AC | 2 ms
6,676 KB |
testcase_04 | AC | 1 ms
6,676 KB |
testcase_05 | AC | 2 ms
6,676 KB |
testcase_06 | AC | 2 ms
6,676 KB |
testcase_07 | AC | 2 ms
6,676 KB |
testcase_08 | AC | 2 ms
6,676 KB |
testcase_09 | AC | 2 ms
6,676 KB |
testcase_10 | AC | 2 ms
6,676 KB |
testcase_11 | AC | 1 ms
6,676 KB |
testcase_12 | AC | 189 ms
23,552 KB |
testcase_13 | AC | 199 ms
23,552 KB |
testcase_14 | AC | 209 ms
23,424 KB |
testcase_15 | AC | 223 ms
24,448 KB |
testcase_16 | AC | 281 ms
36,128 KB |
testcase_17 | AC | 341 ms
47,600 KB |
testcase_18 | AC | 408 ms
58,148 KB |
testcase_19 | AC | 405 ms
64,300 KB |
testcase_20 | AC | 380 ms
64,508 KB |
testcase_21 | AC | 390 ms
65,244 KB |
testcase_22 | AC | 371 ms
65,648 KB |
testcase_23 | AC | 379 ms
65,892 KB |
testcase_24 | AC | 358 ms
65,368 KB |
testcase_25 | AC | 307 ms
45,788 KB |
testcase_26 | AC | 298 ms
55,656 KB |
testcase_27 | AC | 336 ms
65,248 KB |
testcase_28 | AC | 330 ms
64,764 KB |
testcase_29 | AC | 356 ms
65,504 KB |
testcase_30 | AC | 323 ms
44,116 KB |
testcase_31 | AC | 378 ms
56,112 KB |
testcase_32 | AC | 444 ms
65,528 KB |
testcase_33 | AC | 423 ms
67,804 KB |
testcase_34 | AC | 431 ms
68,008 KB |
testcase_35 | AC | 453 ms
68,000 KB |
testcase_36 | AC | 414 ms
68,028 KB |
testcase_37 | AC | 340 ms
68,768 KB |
testcase_38 | AC | 316 ms
45,768 KB |
testcase_39 | AC | 249 ms
61,624 KB |
testcase_40 | AC | 240 ms
61,072 KB |
testcase_41 | AC | 226 ms
60,720 KB |
testcase_42 | AC | 227 ms
60,712 KB |
testcase_43 | AC | 248 ms
59,564 KB |
testcase_44 | AC | 239 ms
48,232 KB |
testcase_45 | AC | 261 ms
57,232 KB |
testcase_46 | AC | 261 ms
66,944 KB |
ソースコード
// -fsanitize=undefined, // #define _GLIBCXX_DEBUG #pragma GCC target("avx2") #pragma GCC optimize("unroll-loops") #include <iostream> #include <vector> #include <string> #include <map> #include <set> #include <queue> #include <algorithm> #include <cmath> #include <iomanip> #include <random> #include <stdio.h> #include <fstream> #include <functional> #include <cassert> #include <unordered_map> #include <bitset> #include <chrono> #include <atcoder/modint> #include <atcoder/convolution> using namespace std; using namespace atcoder; #define rep(i,n) for (int i=0;i<n;i+=1) #define rrep(i,n) for (int i=n-1;i>-1;i--) #define pb push_back #define all(x) (x).begin(), (x).end() #define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << " )\n"; template<class T> using vec = vector<T>; template<class T> using vvec = vec<vec<T>>; template<class T> using vvvec = vec<vvec<T>>; using ll = long long; using pii = pair<int,int>; using pll = pair<ll,ll>; template<class T> bool chmin(T &a, T b){ if (a>b){ a = b; return true; } return false; } template<class T> bool chmax(T &a, T b){ if (a<b){ a = b; return true; } return false; } template<class T> T sum(vec<T> x){ T res=0; for (auto e:x){ res += e; } return res; } template<class T> void printv(vec<T> x){ for (auto e:x){ cout<<e<<" "; } cout<<endl; } template<class T,class U> ostream& operator<<(ostream& os, const pair<T,U>& A){ os << "(" << A.first <<", " << A.second << ")"; return os; } template<class T> ostream& operator<<(ostream& os, const set<T>& S){ os << "set{"; for (auto a:S){ os << a; auto it = S.find(a); it++; if (it!=S.end()){ os << ", "; } } os << "}"; return os; } using mint = modint998244353; ostream& operator<<(ostream& os, const mint& a){ os << a.val(); return os; } template<class T> ostream& operator<<(ostream& os, const vec<T>& A){ os << "["; rep(i,A.size()){ os << A[i]; if (i!=A.size()-1){ os << ", "; } } os << "]" ; return os; } template <typename T> vector<T>& operator+=(vector<T>& a, const vector<T>& b) { if (a.size() < b.size()) { a.resize(b.size()); } for (int i = 0; i < (int)b.size(); i++) { a[i] += b[i]; } return a; } template <typename T> vector<T> operator+(const vector<T>& a, const vector<T>& b) { vector<T> c = a; return c += b; } int main(){ ios::sync_with_stdio(false); std::cin.tie(nullptr); int N,M; cin>>N>>M; vec<vec<int>> edge(N); vec<set<int>> to_big(N); rep(i,M){ int u,v; cin>>u>>v; u--; v--; edge[max(u,v)].push_back(min(u,v)); to_big[min(u,v)].insert(max(u,v)); } vector<mint> dp(N,1); vector<mint> lazy_add(N,0); vector<int> root(N,-1); vector<vector<int>> G(N); vector<map<int,mint>> add_to_big(N); rep(i,N){ root[i] = i; G[i].push_back(i); } auto merge = [&](int u,int v){ u = root[u]; v = root[v]; if (u == v) return ; if (G[u].size() > G[v].size()) swap(u,v); for (auto x:G[u]){ root[x] = v; G[v].push_back(x); } G[u].clear(); for (auto [big,val]:add_to_big[u]){ if (!add_to_big[v].count(big)){ add_to_big[v][big] = -lazy_add[v]; } add_to_big[v][big] += lazy_add[u] + val; } }; for (int i=0;i<N;i++){ set<int> done; for (auto nv:edge[i]){ int r = root[nv]; if (done.count(r)) continue; if (add_to_big[r].count(i)){ dp[i] += add_to_big[r][i] + lazy_add[r]; add_to_big[r].erase(i); } } for (auto nv:to_big[i]){ add_to_big[i][nv] = 0; } for (auto nv:edge[i]){ merge(nv,i); } lazy_add[root[i]] += dp[i]; } mint ans = accumulate(all(dp),mint(0)); //debug(dp); cout << ans << endl; }