結果
問題 | No.1290 Addition and Subtraction Operation |
ユーザー | Cinnamoroll |
提出日時 | 2020-08-03 22:53:40 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 8,394 bytes |
コンパイル時間 | 2,844 ms |
コンパイル使用メモリ | 201,236 KB |
実行使用メモリ | 41,336 KB |
最終ジャッジ日時 | 2024-07-22 20:12:36 |
合計ジャッジ時間 | 8,879 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 5 ms
6,528 KB |
testcase_01 | AC | 4 ms
6,400 KB |
testcase_02 | WA | - |
testcase_03 | AC | 4 ms
6,400 KB |
testcase_04 | WA | - |
testcase_05 | AC | 4 ms
6,400 KB |
testcase_06 | AC | 5 ms
6,400 KB |
testcase_07 | AC | 5 ms
6,528 KB |
testcase_08 | WA | - |
testcase_09 | AC | 5 ms
6,528 KB |
testcase_10 | AC | 4 ms
6,528 KB |
testcase_11 | AC | 5 ms
6,272 KB |
testcase_12 | AC | 5 ms
6,272 KB |
testcase_13 | WA | - |
testcase_14 | WA | - |
testcase_15 | AC | 4 ms
6,400 KB |
testcase_16 | AC | 4 ms
6,400 KB |
testcase_17 | AC | 5 ms
6,400 KB |
testcase_18 | AC | 4 ms
6,400 KB |
testcase_19 | AC | 4 ms
6,400 KB |
testcase_20 | AC | 4 ms
6,400 KB |
testcase_21 | AC | 5 ms
6,400 KB |
testcase_22 | WA | - |
testcase_23 | AC | 4 ms
6,528 KB |
testcase_24 | AC | 5 ms
6,400 KB |
testcase_25 | AC | 5 ms
6,400 KB |
testcase_26 | AC | 4 ms
6,400 KB |
testcase_27 | WA | - |
testcase_28 | AC | 5 ms
6,528 KB |
testcase_29 | AC | 4 ms
6,400 KB |
testcase_30 | AC | 4 ms
6,528 KB |
testcase_31 | AC | 5 ms
6,400 KB |
testcase_32 | AC | 4 ms
6,528 KB |
testcase_33 | WA | - |
testcase_34 | AC | 4 ms
6,272 KB |
testcase_35 | WA | - |
testcase_36 | AC | 4 ms
6,528 KB |
testcase_37 | AC | 5 ms
6,528 KB |
testcase_38 | AC | 4 ms
6,528 KB |
testcase_39 | AC | 4 ms
6,400 KB |
testcase_40 | AC | 4 ms
6,400 KB |
testcase_41 | AC | 4 ms
6,400 KB |
testcase_42 | AC | 21 ms
8,516 KB |
testcase_43 | AC | 21 ms
8,512 KB |
testcase_44 | AC | 22 ms
8,512 KB |
testcase_45 | AC | 22 ms
8,516 KB |
testcase_46 | AC | 22 ms
8,512 KB |
testcase_47 | AC | 21 ms
8,388 KB |
testcase_48 | AC | 22 ms
8,516 KB |
testcase_49 | AC | 22 ms
8,388 KB |
testcase_50 | AC | 21 ms
8,520 KB |
testcase_51 | AC | 22 ms
8,516 KB |
testcase_52 | AC | 22 ms
8,516 KB |
testcase_53 | AC | 22 ms
8,516 KB |
testcase_54 | AC | 22 ms
8,388 KB |
testcase_55 | AC | 21 ms
8,516 KB |
testcase_56 | AC | 21 ms
8,512 KB |
testcase_57 | AC | 103 ms
38,016 KB |
testcase_58 | AC | 119 ms
35,656 KB |
testcase_59 | AC | 104 ms
38,400 KB |
testcase_60 | AC | 114 ms
29,408 KB |
testcase_61 | AC | 119 ms
32,100 KB |
testcase_62 | AC | 118 ms
31,208 KB |
testcase_63 | AC | 111 ms
35,792 KB |
testcase_64 | AC | 98 ms
41,088 KB |
testcase_65 | AC | 93 ms
39,552 KB |
testcase_66 | AC | 115 ms
34,144 KB |
testcase_67 | AC | 114 ms
28,884 KB |
testcase_68 | AC | 119 ms
31,960 KB |
testcase_69 | AC | 115 ms
35,784 KB |
testcase_70 | AC | 111 ms
36,812 KB |
testcase_71 | AC | 124 ms
34,508 KB |
testcase_72 | AC | 96 ms
39,552 KB |
testcase_73 | AC | 117 ms
33,352 KB |
testcase_74 | AC | 103 ms
41,336 KB |
testcase_75 | AC | 93 ms
40,192 KB |
testcase_76 | AC | 109 ms
36,420 KB |
testcase_77 | AC | 136 ms
31,708 KB |
testcase_78 | AC | 137 ms
32,960 KB |
testcase_79 | AC | 133 ms
36,992 KB |
testcase_80 | AC | 136 ms
29,660 KB |
testcase_81 | AC | 141 ms
29,780 KB |
testcase_82 | WA | - |
testcase_83 | WA | - |
testcase_84 | WA | - |
testcase_85 | WA | - |
testcase_86 | WA | - |
ソースコード
// warm heart, wagging tail,and a smile just for you! // ███████████ // ███╬╬╬╬╬╬╬╬╬╬███ // ███╬╬╬╬╬████╬╬╬╬╬╬███ // ███████████ ██╬╬╬╬╬████╬╬████╬╬╬╬╬██ // █████████╬╬╬╬╬████████████╬╬╬╬╬██╬╬╬╬╬╬███╬╬╬╬╬██ // ████████╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬█████████╬╬╬╬╬╬██╬╬╬╬╬╬╬██ // ████╬██╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬█████████╬╬╬╬╬╬╬╬╬╬╬██ // ███╬╬╬█╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬██╬╬███╬╬╬╬╬╬╬█████ // ███╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬██╬╬╬████████╬╬╬╬╬██ // ███╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬███╬╬╬╬╬╬╬╬╬███ // ███╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬█████╬╬╬╬╬╬╬██ // ████╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬████╬╬╬╬╬████ // █████████████╬╬╬╬╬╬╬╬██╬╬╬╬╬████╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬█████╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬███╬╬╬╬██████ // ████╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬██╬╬██████╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬██████╬╬╬╬╬╬╬███████████╬╬╬╬╬╬╬╬██╬╬╬██╬╬╬██ // ███╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬██╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬██╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬████╬╬╬╬╬╬╬╬╬╬╬█╬╬╬╬╬╬╬██╬╬╬╬╬╬╬╬██ // ██╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬██╬╬╬╬▓▓▓▓▓▓╬╬╬████╬╬████╬╬╬╬╬╬╬▓▓▓▓▓▓▓▓██╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬██╬╬╬╬╬╬╬███ // ██╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬██████▓▓▓▓▓▓▓╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬▓▓▓▓▓▓▓██╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬██╬╬╬╬█████ // ███╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬███╬╬╬╬╬██╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬█████╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬████████ // ███╬╬╬╬╬╬╬╬╬╬╬╬╬█████╬╬╬╬╬╬╬╬██╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬███╬╬██╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬██ // ██████████████ ████╬╬╬╬╬╬███████████████████████████╬╬╬╬╬██╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬████ // ███████ █████ ███████████████████ // #include "bits/stdc++.h" using namespace std; #define INF (1<<30) #define LINF (1LL<<60) #define fs first #define sc second #define int long long #define FOR(i,a,b) for(int i=(a);i<(b);++i) #define RFOR(i,a,b) for(int i = (b-1);i>=(a);--i) #define REP(i,n) FOR(i,0,(n)) #define RREP(i,n) RFOR(i,0,(n)) #define ITR(itr,mp) for(auto itr = (mp).begin(); itr != (mp).end(); ++itr) #define RITR(itr,mp) for(auto itr = (mp).rbegin(); itr != (mp).rend(); ++itr) #define range(i,a,b) ((a)<=(i) && (i)<(b)) #define debug(x) cout << #x << " = " << (x) << endl #define SP << " " << template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;} template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;} #define MSB(x) (63-__builtin_clzll(x)) #define pcnt(x) (__builtin_popcountll(x)) #define parity(i,j) (i&(1LL<<j)) typedef pair<int,int> P; typedef tuple<int,int,int> T; typedef vector<int> vec; typedef vector<vector<int>> mat; struct UnionFind { private: vector<int> child,tree; vector<vector<int>> list; public: UnionFind(int v) { tree.resize(v); list.resize(v); REP(i,v) tree[i] = i, list[i].push_back(i); } int root(int i){ if(i == tree[i]){ REP(j,child.size()) tree[child[j]] = i; child.clear(); return i; } else{ child.push_back(i); return i = root(tree[i]); } } int size(int i){ return list[root(i)].size(); } vector<int> nodes(int no){ return list[root(no)]; } bool unit(int x, int y){ x = root(x); y = root(y); if(x==y) return false; if(list[x].size() < list[y].size()) swap(x,y); for(int no:list[y]) list[x].emplace_back(no); tree[y] = x; return true; } bool isUnit(int x, int y){ return root(x) == root(y); } }; void ng(){ cout << "NO" << endl; exit(0); } const int N = 1e5+10; vector<int> edge[N],color(N,0); bool isBip(int no){ if(!color[no]) color[no] = 1; bool flag = true; for(auto to:edge[no]){ if(color[no]==color[to]) flag = false; else if(!color[to]){ color[to] = -color[no]; if(!isBip(to)) flag = false; } } return flag; } signed main(){ ios::sync_with_stdio(false); cin.tie(0); int n,m; cin >> n >> m; vector<int> b(n+2); REP(i,n) cin >> b[i+1]; vector<int> d(n+1); REP(i,n+1) d[i] = b[i]+b[i+1]; UnionFind uf(n+1); vector<P> op; REP(i,m){ int x,y; cin >> x >> y; if((y-x)%2) uf.unit(x-1,y); else op.emplace_back(x-1,y); } // 連結成分で座圧 map<int,int> mp; REP(i,n+1) mp[uf.root(i)]++; int k = 0; // 連結成分数 ITR(itr,mp) itr->sc = k++; vector<int> id(n+1),sum(k,0); // 座圧後のid, 連結成分内のdのsum REP(i,n+1){ id[i] = mp[uf.root(i)]; sum[id[i]] += d[i]; } vector<int> flag(k,0); // 自己ループを含むか UnionFind uf2(k); REP(i,op.size()){ int x = id[op[i].fs], y = id[op[i].sc]; if(x==y) flag[x]++; else{ uf2.unit(x,y); edge[x].emplace_back(y); edge[y].emplace_back(x); } } map<int,int> sum2; vector<int> flag2(k,0), list[k]; REP(i,k){ sum2[uf2.root(i)] += sum[i]; flag2[uf2.root(i)] += flag[i]; list[uf2.root(i)].emplace_back(i); } REP(i,k){ if(uf2.root(i)!=i) continue; if(sum2[i]%2) ng(); // 総和を奇数にはできない if(flag2[i]) continue; // 自己ループ //if(!isBip(i)) continue; // 奇閉路ある? int v = 0; for(int no:list[i]) v += sum[no]*color[no]; if(v) ng(); // 和が一致する? } cout << "YES" << endl; return 0; }