結果
問題 | No.1194 Replace |
ユーザー | mugen_1337 |
提出日時 | 2020-08-27 19:34:54 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 3,283 bytes |
コンパイル時間 | 3,697 ms |
コンパイル使用メモリ | 223,892 KB |
実行使用メモリ | 128,308 KB |
最終ジャッジ日時 | 2024-11-08 01:27:45 |
合計ジャッジ時間 | 23,729 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | WA | - |
testcase_01 | WA | - |
testcase_02 | WA | - |
testcase_03 | WA | - |
testcase_04 | WA | - |
testcase_05 | WA | - |
testcase_06 | WA | - |
testcase_07 | WA | - |
testcase_08 | WA | - |
testcase_09 | WA | - |
testcase_10 | WA | - |
testcase_11 | WA | - |
testcase_12 | WA | - |
testcase_13 | WA | - |
testcase_14 | WA | - |
testcase_15 | WA | - |
testcase_16 | WA | - |
testcase_17 | WA | - |
testcase_18 | WA | - |
testcase_19 | WA | - |
testcase_20 | AC | 2 ms
5,248 KB |
testcase_21 | AC | 2 ms
5,248 KB |
testcase_22 | AC | 2 ms
5,248 KB |
testcase_23 | WA | - |
testcase_24 | WA | - |
testcase_25 | AC | 14 ms
5,248 KB |
testcase_26 | AC | 152 ms
17,092 KB |
testcase_27 | AC | 20 ms
5,248 KB |
testcase_28 | AC | 63 ms
10,212 KB |
testcase_29 | WA | - |
ソースコード
#include<bits/stdc++.h>using namespace std;#define ALL(x) x.begin(),x.end()#define rep(i,n) for(int i=0;i<(n);i++)#define debug(v) cout<<#v<<":";for(auto x:v){cout<<x<<' ';}cout<<endl;#define mod 1000000007using ll=long long;const int INF=1000000000;const ll LINF=1001002003004005006ll;int dx[]={1,0,-1,0},dy[]={0,1,0,-1};// ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return true;}return false;}template<class T>bool chmin(T &a,const T &b){if(b<a){a=b;return true;}return false;}struct IOSetup{IOSetup(){cin.tie(0);ios::sync_with_stdio(0);cout<<fixed<<setprecision(12);}} iosetup;template<typename T1,typename T2>ostream &operator<<(ostream &os,const pair<T1,T2>&p){os<<p.first<<" "<<p.second;return os;}template<typename T>ostream &operator<<(ostream &os,const vector<T>&v){for(int i=0;i<(int)v.size();i++) os<<v[i]<<(i+1==(int)v.size()?"":" ");return os;}template<typename T1,typename T2>istream &operator>>(istream &is,pair<T1,T2>&p){is>>p.first>>p.second;return is;}template<typename T>istream &operator>>(istream &is,vector<T>&v){for(T &x:v)is>>x;return is;}struct StronglyConnectedComponents{vector<vector<int>> g;vector<vector<int>> to,from;vector<int> comp,order,used;StronglyConnectedComponents(vector<vector<int>> &g):g(g),to(g.size()),from(g.size()),comp(g.size(),-1),used(g.size()){for(int i=0;i<(int)g.size();i++){for(auto x:g[i]){to[i].push_back(x);from[x].push_back(i);}}}int operator[](int k){return comp[k];}void dfs(int now){if(used[now]) return ;used[now]=true;for(int x:to[now])dfs(x);order.push_back(now);}void rdfs(int now,int cnt){if(comp[now]!=-1) return ;comp[now]=cnt;for(int x:from[now]) rdfs(x,cnt);}vector<vector<int>> build(){vector<vector<int>> t;for(int i=0;i<(int)to.size();i++) dfs(i);reverse(order.begin(),order.end());int ptr=0;for(int i:order)if(comp[i]==-1)rdfs(i,ptr),ptr++;t.resize(ptr);for(int i=0;i<(int)g.size();i++){for(auto v:to[i]){int x=comp[i],y=comp[v];if(x==y) continue;t[x].push_back(y);}}return t;}};signed main(){int n,m;cin>>n>>m;vector<vector<int>> g;int sz=0;map<int,int> id,rev;vector<pair<int,int>> es;rep(i,m){int u,v;cin>>u>>v;u--,v--;if(!id.count(u)) id[u]=sz++;if(!id.count(v)) id[v]=sz++;es.push_back({u,v});}for(auto p:id)rev[p.second]=p.first;g.resize(sz);for(auto [u,v]:es) g[id[u]].push_back(id[v]);StronglyConnectedComponents scc(g);auto t=scc.build();vector<ll> v(t.size());for(auto [label,node]:id){chmax(v[scc[node]],(ll)label);}for(int i=(int)t.size()-1;i>=0;i--){for(auto j:t[i]) chmax(v[i],v[j]);}ll res=n*(n+1)/2;for(auto [label,node]:id) res+=v[scc[node]]-label;cout<<res<<endl;return 0;}