結果
問題 | No.1194 Replace |
ユーザー | yukudo |
提出日時 | 2020-09-02 14:14:35 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
RE
|
実行時間 | - |
コード長 | 2,979 bytes |
コンパイル時間 | 2,510 ms |
コンパイル使用メモリ | 191,600 KB |
実行使用メモリ | 35,184 KB |
最終ジャッジ日時 | 2024-05-01 10:31:30 |
合計ジャッジ時間 | 21,444 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | RE | - |
testcase_01 | RE | - |
testcase_02 | RE | - |
testcase_03 | RE | - |
testcase_04 | RE | - |
testcase_05 | RE | - |
testcase_06 | RE | - |
testcase_07 | RE | - |
testcase_08 | RE | - |
testcase_09 | RE | - |
testcase_10 | RE | - |
testcase_11 | RE | - |
testcase_12 | RE | - |
testcase_13 | RE | - |
testcase_14 | AC | 310 ms
25,124 KB |
testcase_15 | RE | - |
testcase_16 | RE | - |
testcase_17 | AC | 223 ms
24,404 KB |
testcase_18 | AC | 212 ms
22,896 KB |
testcase_19 | RE | - |
testcase_20 | AC | 8 ms
9,344 KB |
testcase_21 | AC | 8 ms
9,472 KB |
testcase_22 | AC | 7 ms
9,472 KB |
testcase_23 | AC | 89 ms
16,688 KB |
testcase_24 | AC | 30 ms
12,140 KB |
testcase_25 | AC | 18 ms
9,924 KB |
testcase_26 | AC | 103 ms
16,008 KB |
testcase_27 | AC | 24 ms
10,364 KB |
testcase_28 | AC | 53 ms
12,548 KB |
testcase_29 | AC | 11 ms
9,856 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define REP(i,n) for(int i=0,_n=(int)(n);i<_n;++i) #define ALL(v) (v).begin(),(v).end() #define CLR(t,v) memset(t,(v),sizeof(t)) template<class T1,class T2>ostream& operator<<(ostream& os,const pair<T1,T2>&a){return os<<"("<<a.first<<","<<a.second<< ")";} template<class T>void pv(T a,T b){for(T i=a;i!=b;++i)cout<<(*i)<<" ";cout<<endl;} template<class T>void chmin(T&a,const T&b){if(a>b)a=b;} template<class T>void chmax(T&a,const T&b){if(a<b)a=b;} ll nextLong() { ll x; scanf("%lld", &x); return x;} const int MAX_N = 112345; vector<int> g[MAX_N]; vector<int> r[MAX_N]; int sccid[MAX_N]; int sccnum; void dfs(int p, vector<int>& order) { if (sccid[p] != 0) return; sccid[p] = 1; for (int i : g[p]) dfs(i, order); order.push_back(p); } void rdfs(int p, int id) { if (sccid[p] != -1) return; sccid[p] = id; for (int i : r[p]) rdfs(i, id); } void scc(int N) { vector<int> order; CLR(sccid, 0); REP(i, N) dfs(i, order); CLR(sccid, -1); sccnum = 0; for (int i = (int)order.size() - 1; i >= 0; i--) if (sccid[order[i]] == -1) { rdfs(order[i], sccnum); sccnum++; } } // 座標圧縮 vector<ll> rev; // 圧縮後の値から元の値への写像 vector<int> normalize(const vector<ll> v) { const int N = v.size(); vector<int> res(N); vector<pair<ll,int> > t(N); rev = vector<ll>(N); REP(i, N) t[i] = { v[i], i }; sort(ALL(t)); int r = 0; REP(i, N) { r += (i > 0 && t[i - 1].first != t[i].first); res[t[i].second] = r; rev[r] = t[i].first; } rev.erase(rev.begin() + r + 1, rev.end()); return res; } int main2() { REP(i, MAX_N) g[i].clear(); REP(i, MAX_N) r[i].clear(); int N = nextLong(); int M = nextLong(); vector<ll> es_row(2 * M); REP(i, M) { int a = nextLong(); int b = nextLong(); es_row[2 * i ] = a; es_row[2 * i + 1] = b; } auto es = normalize(es_row); // pv(ALL(rev)); ll ans = (ll)(N+1)*N/2; for (auto x : set<ll>(ALL(es_row))) { ans -= x; } REP(i, M) { int a = es[i * 2]; int b = es[i * 2 + 1]; g[a].push_back(b); r[b].push_back(a); } int V = rev.size(); scc(V); vector<vector<int>> gg(sccnum); vector<int> scc_size(sccnum); vector<ll> scc_max(sccnum); REP(i, V) { scc_size[sccid[i]]++; for (int j : g[i]) { if (sccid[i] != sccid[j]) gg[sccid[i]].push_back(sccid[j]); } chmax(scc_max[sccid[i]], rev[i]); } REP(s, sccnum) { sort(ALL(gg[s])); gg[s].erase(unique(ALL(gg[s])), gg[s].end()); // cout << s << " : "; pv(ALL(gg[s])); } // cout << "size: "; pv(ALL(scc_size)); // cout << "max: "; pv(ALL(scc_max)); for (int s = sccnum - 1; s >= 0; s--) { for (int nxt : gg[s]) { chmax(scc_max[s], scc_max[nxt]); } ans += scc_max[s] * scc_size[s]; } cout << ans << endl; return 0; } int main() { #ifdef LOCAL for (;!cin.eof();cin>>ws) #endif main2(); return 0; }