Submission #1195590

#TimeUsernameProblemLanguageResultExecution timeMemory
1195590vnedu전압 (JOI14_voltage)C++17
10 / 100
213 ms4164 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]; vector<int> adj[N]; namespace sub1 { bool check() { return (n<=1000 && m<=2000); } const int N = 1e3 + 10; bool vis[N]; int dep[N]; void dfs(int u) { vis[u]=1; for(int v : adj[u]) if(!vis[v]) { dep[v]=dep[u]+1; dfs(v); } } void solve() { int ans=0; for(int tri=1;tri<=m;++tri) { for(int i=0;i<=n;++i) vector<int>().swap(adj[i]); for(int i=1;i<=m;++i) if(i!=tri) { int u=edge[i].fi,v=edge[i].se; adj[u].pb(v); adj[v].pb(u); } adj[0].pb(edge[tri].fi); adj[edge[tri].fi].pb(0); adj[0].pb(edge[tri].se); adj[edge[tri].se].pb(0); memset(vis,0,sizeof(vis)); for(int i=0;i<=n;++i) if(!vis[i]) { dep[i]=1; dfs(i); } bool ok=1; edge[0]={0,edge[tri].fi}; edge[m+1]={0,edge[tri].se}; for(int i=0;i<=m+1;++i) if(i!=tri) { int du=dep[edge[i].fi]; int dv=dep[edge[i].se]; ok&=((du&1)!=(dv&1)); } ans+=ok; } cout<<ans; } } void solve() { cin>>n>>m; for(int i=1;i<=m;++i) cin>>edge[i].fi>>edge[i].se; if(sub1::check()) return void(sub1::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...