| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 43277 |
2018-03-13T00:41:47 Z |
smu201111192 |
전압 (JOI14_voltage) |
C++14 |
|
317 ms |
44852 KB |
#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <cstring>
using namespace std;
const int MAXN = 200005;
int par[MAXN][20],dep[MAXN],n,m,low[MAXN],dfn[MAXN],step = 0,bridge[MAXN],color[MAXN],tedge[MAXN];
int dp[MAXN],chk[MAXN],pedge[MAXN];
vector<int> bad;
vector<pair<int,int> > adj[MAXN],tree[MAXN];
map<pair<int,int>,vector<int> > mp;
pair<int,int> e[MAXN];
void dfs(int here,int dad,int d,int c){
dfn[here] = 1;
color[here] = c;
dep[here] = d;
par[here][0] = dad;
for(int i = 0; i < tree[here].size();i++){
int there = tree[here][i].first;
if(there == dad) continue;
dfs(there,here,d+1,c^1);
}
}
int getLca(int u,int v){
if(dep[u] > dep[v]) swap(u,v);
int diff = dep[v] - dep[u];
int i = 0;
while(diff){
if(diff & (1<<i)) { diff -= (1<<i); v = par[v][i];}
i++;
}
if(u == v)return u;
for(int i = 19 ; i >=0 ;i--){
if(par[u][i] != par[v][i]){ u = par[u][i],v = par[v][i]; }
}
return par[u][0];
}
void getTree(int here,int dad){
low[here] = dfn[here] = ++step;
for(int i = 0 ; i < adj[here].size();i++){
int there = adj[here][i].first;
int eid = adj[here][i].second;
if(!dfn[there]){
tedge[eid] = 1;
getTree(there,here);
low[here] = min(low[here],low[there]);
tree[here].push_back({there,eid});
tree[there].push_back({here,eid});
if(low[there] > dfn[here] && mp[{min(here,there),max(here,there)}].size() <= 1) bridge[eid] = 1;
}
else if(there != dad && dfn[there] < dfn[here]){
low[here] = min(low[here],dfn[there]);
}
}
}
void solve(int here,int dad){
dfn[here] = 1;
for(int i = 0; i < tree[here].size(); i++){
int there = tree[here][i].first;
int eid = tree[here][i].second;
if(there == dad) continue;
pedge[there] = eid;
solve(there,here);
dp[here] += dp[there];
}
}
int main(){
ios::sync_with_stdio(false); cin.tie(0);
cin >> n >> m;
vector<pair<int,int> > ret;
for(int i = 1; i <= m; i++){
int u,v; cin>>u>>v;
e[i] = make_pair(u,v);
adj[u].push_back({v,i});
adj[v].push_back({u,i});
mp[{min(u,v),max(u,v)}].push_back(i);
}
for(int i = 1; i <= n; i++){
if(!dfn[i]) getTree(i,-1);
}
for(int i = 1; i <= m; i++){
if(tedge[i]){
int u = e[i].first;
int v = e[i].second;
}
}
memset(dfn,0,sizeof(dfn));
for(int i = 1; i <= n; i++){
if(!dfn[i]) dfs(i,-1,0,0);
}
for(int i = 1; i < 20; i++) for(int j = 1; j <= n; j++){
if(par[j][i-1] == -1) par[j][i] = -1;
else par[j][i] = par[par[j][i-1]][i-1];
}
int bcnt = 0;
set<int> bbd;
for(int i = 1; i <= m ;i++) if(bridge[i]) bcnt++;
for(int i = 1; i <= n; i++){
for(int j = 0; j < adj[i].size(); j++){
int u = i;
int v = adj[i][j].first;
int eid = adj[i][j].second;
if(tedge[eid]) continue;
if(color[u] == color[v] && dfn[u] && dfn[v]) bbd.insert(adj[i][j].second);
}
}
bad.assign(bbd.begin(),bbd.end());
if(bad.size() >= 2){
cout<<0; exit(0);
}
else if(bad.size() == 0){
cout<<m - bcnt;
exit(0);
}
else{
for(int i = 1; i <= m; i++){
if(!tedge[i]){
//not tree edge
int u = e[i].first; int v = e[i].second;
if(color[u] == color[v]) continue;
int lca = getLca(u,v);
vector<int> &vv = mp[{min(u,v),max(u,v)}];
for(auto x:vv){
chk[x] = 1;
}
dp[u]++;
dp[v]++;
dp[lca] -= 2;
}
}
memset(dfn,0,sizeof(dfn));
for(int i = 1; i <= n; i++) if(!dfn[i])solve(i,-1);
for(int i = 1; i <= n; i++){
if(dp[i] > 0){
chk[pedge[i]] = 1; // not bridge면서 !chk 인것들개수
}
}
int ans = 0;
for(int i = 1; i <= m; i++){
ans += (!bridge[i] && !chk[i]);
}
cout<<ans;
exit(0);
}
return 0;
}
Compilation message
voltage.cpp: In function 'void dfs(int, int, int, int)':
voltage.cpp:20:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < tree[here].size();i++){
^
voltage.cpp: In function 'void getTree(int, int)':
voltage.cpp:43:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0 ; i < adj[here].size();i++){
^
voltage.cpp: In function 'void solve(int, int)':
voltage.cpp:61:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < tree[here].size(); i++){
^
voltage.cpp: In function 'int main()':
voltage.cpp:86:17: warning: unused variable 'u' [-Wunused-variable]
int u = e[i].first;
^
voltage.cpp:87:17: warning: unused variable 'v' [-Wunused-variable]
int v = e[i].second;
^
voltage.cpp:102:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = 0; j < adj[i].size(); j++){
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
11000 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
317 ms |
41288 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
118 ms |
42124 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
164 ms |
44852 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
