제출 #1195900

#제출 시각아이디문제언어결과실행 시간메모리
1195900vnedu전압 (JOI14_voltage)C++17
100 / 100
99 ms18248 KiB
#include<bits/stdc++.h> using namespace std; typedef long long ll; template<class T> bool maximize(T &a, const T &b){ return (a < b ? a = b, 1 : 0); } template<class T> bool minimize(T &a, const T &b){ return (a > b ? a = b, 1 : 0); } #define fi first #define se second #define pb push_back #define ii pair<int, int> #define all(x) x.begin(), x.end() #define TASK "nonsense" /// end of template /// const int N = 1e5 + 10; const int M = 2e5 + 10; int n,m; ii edge[M]; namespace subfull { vector<ii> adj[N]; int dep[N],parId[N],sum[N][2],num[2],pass[M][2]; void dfs(int u) { for(ii p : adj[u]) if(dep[p.fi]==-1) { // cout<<u<<' '<<p.fi<<'\n'; dep[p.fi]=dep[u]+1; parId[p.fi]=p.se; dfs(p.fi); } } void work(int u) { for(ii p : adj[u]) if(parId[p.fi]==p.se) { work(p.fi); for(int j=0;j<2;++j) sum[u][j]+=sum[p.fi][j]; } if(parId[u]!=-1) { pass[parId[u]][0]=sum[u][0]; pass[parId[u]][1]=sum[u][1]; } } void solve() { for(int i=1;i<=m;++i) { adj[edge[i].fi].pb({edge[i].se,i}); adj[edge[i].se].pb({edge[i].fi,i}); } memset(dep,-1,sizeof(dep)); memset(parId,-1,sizeof(parId)); for(int i=1;i<=n;++i) if(dep[i]==-1) { dep[i]=1; dfs(i); } for(int i=1;i<=m;++i) { int u=edge[i].fi,v=edge[i].se; if(dep[u]>dep[v]) swap(u,v); if(parId[v]!=i) { bool con=((dep[u]&1)!=(dep[v]&1)); ++sum[v][con]; --sum[u][con]; ++num[con]; ++pass[i][con]; } } for(int i=1;i<=n;++i) if(dep[i]==1) work(i); int ans=0; for(int i=1;i<=m;++i) if((pass[i][0]==num[0]) && pass[i][1]==0) ++ans; cout<<ans; } } void solve() { cin>>n>>m; for(int i=1;i<=m;++i) cin>>edge[i].fi>>edge[i].se; return void(subfull::solve()); } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); // freopen(TASK".inp","r",stdin); // freopen(TASK".out","w",stdout); int testcase=1; // cin>>testcase; while (testcase--) solve(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...