#include<iostream> #include "sabotaz.h" #include "message.h" #include<algorithm> #include<vector> #define st first #define nd second #define mp make_pair #define PII pair<int,int> #define pb push_back #define LL long long using namespace std; vector<PII>g[200000]; int pre[200000],e_ojc[200000],ojc[200000],low[200000],t; bool odw[200000]; void preorder(int x){ pre[x]=t++; odw[x]=1; for(int i=0;i<g[x].size();i++){ if(odw[g[x][i].st])continue; e_ojc[g[x][i].st]=g[x][i].nd; ojc[g[x][i].st]=x; preorder(g[x][i].st); } } void licz_low(int x){ low[x]=pre[x]; odw[x]=1; for(int i=0;i<g[x].size();i++){ if(odw[g[x][i].st])continue; licz_low(g[x][i].st); low[x]=min(low[x],low[g[x][i].st]); } for(int i=0;i<g[x].size();i++){ int w=g[x][i].st; if(pre[w]>pre[x])continue; if(g[x][i].nd!=e_ojc[x])low[x]=min(low[x],low[w]); } } LL f(LL x){ return ((x+1000000007)*1000000033); } vector<int>wys[100]; int razy[2000000]; main(){ //duzo spsk!!! //get_test(); int nr=MyNodeId(),ins=NumberOfNodes(); int E=NumberOfBridges(); if(E<=1000000){ ins=1; if(nr>0)return 0; } int n=NumberOfIsles(); if(E>1000000){ for(int i=nr;i<E;i+=ins){ int x=i; for(int j=0;j<7;j++){ int a=BridgeEndA(x),b=BridgeEndB(x); g[a].pb(mp(b,x)); g[b].pb(mp(a,x)); x=f(x)%E; } } } else{ for(int i=0;i<E;i++){ int a=BridgeEndA(i),b=BridgeEndB(i); g[a].pb(mp(b,i)); g[b].pb(mp(a,i)); } } for(int i=0;i<n;i++){ if(!odw[i]){ ojc[i]=-1; preorder(i); } } for(int i=0;i<n;i++)odw[i]=0; for(int i=0;i<n;i++){ if(!odw[i])licz_low(i); } vector<int>res; for(int i=0;i<n;i++){ if(ojc[i]==-1)continue; if(low[ojc[i]]!=low[i])res.pb(e_ojc[i]); } /*cout<<"mosty\n"; for(int i=0;i<res.size();i++)cout<<res[i]<<" "; cout<<"\n";*/ if(E<=1000000){ cout<<res.size()<<"\n"; return 0; } //komunikacja for(int i=0;i<res.size();i++){ wys[res[i]%ins].pb(res[i]); } for(int i=0;i<ins;i++){ PutInt(i,wys[i].size()); for(int j=0;j<wys[i].size();j++)PutInt(i,wys[i][j]); Send(i); } for(int i=0;i<ins;i++){ Receive(i); int ile=GetInt(i); for(int j=0;j<ile;j++){ razy[GetInt(i)/ins]++; } } int wynik=0; for(int i=0;i<2000000;i++){ if(razy[i]>=3)wynik++; } PutInt(0,wynik); Send(0); if(nr>0)return 0; wynik=0; for(int i=0;i<ins;i++){ Receive(i); wynik+=GetInt(i); } cout<<wynik<<"\n"; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 | #include<iostream> #include "sabotaz.h" #include "message.h" #include<algorithm> #include<vector> #define st first #define nd second #define mp make_pair #define PII pair<int,int> #define pb push_back #define LL long long using namespace std; vector<PII>g[200000]; int pre[200000],e_ojc[200000],ojc[200000],low[200000],t; bool odw[200000]; void preorder(int x){ pre[x]=t++; odw[x]=1; for(int i=0;i<g[x].size();i++){ if(odw[g[x][i].st])continue; e_ojc[g[x][i].st]=g[x][i].nd; ojc[g[x][i].st]=x; preorder(g[x][i].st); } } void licz_low(int x){ low[x]=pre[x]; odw[x]=1; for(int i=0;i<g[x].size();i++){ if(odw[g[x][i].st])continue; licz_low(g[x][i].st); low[x]=min(low[x],low[g[x][i].st]); } for(int i=0;i<g[x].size();i++){ int w=g[x][i].st; if(pre[w]>pre[x])continue; if(g[x][i].nd!=e_ojc[x])low[x]=min(low[x],low[w]); } } LL f(LL x){ return ((x+1000000007)*1000000033); } vector<int>wys[100]; int razy[2000000]; main(){ //duzo spsk!!! //get_test(); int nr=MyNodeId(),ins=NumberOfNodes(); int E=NumberOfBridges(); if(E<=1000000){ ins=1; if(nr>0)return 0; } int n=NumberOfIsles(); if(E>1000000){ for(int i=nr;i<E;i+=ins){ int x=i; for(int j=0;j<7;j++){ int a=BridgeEndA(x),b=BridgeEndB(x); g[a].pb(mp(b,x)); g[b].pb(mp(a,x)); x=f(x)%E; } } } else{ for(int i=0;i<E;i++){ int a=BridgeEndA(i),b=BridgeEndB(i); g[a].pb(mp(b,i)); g[b].pb(mp(a,i)); } } for(int i=0;i<n;i++){ if(!odw[i]){ ojc[i]=-1; preorder(i); } } for(int i=0;i<n;i++)odw[i]=0; for(int i=0;i<n;i++){ if(!odw[i])licz_low(i); } vector<int>res; for(int i=0;i<n;i++){ if(ojc[i]==-1)continue; if(low[ojc[i]]!=low[i])res.pb(e_ojc[i]); } /*cout<<"mosty\n"; for(int i=0;i<res.size();i++)cout<<res[i]<<" "; cout<<"\n";*/ if(E<=1000000){ cout<<res.size()<<"\n"; return 0; } //komunikacja for(int i=0;i<res.size();i++){ wys[res[i]%ins].pb(res[i]); } for(int i=0;i<ins;i++){ PutInt(i,wys[i].size()); for(int j=0;j<wys[i].size();j++)PutInt(i,wys[i][j]); Send(i); } for(int i=0;i<ins;i++){ Receive(i); int ile=GetInt(i); for(int j=0;j<ile;j++){ razy[GetInt(i)/ins]++; } } int wynik=0; for(int i=0;i<2000000;i++){ if(razy[i]>=3)wynik++; } PutInt(0,wynik); Send(0); if(nr>0)return 0; wynik=0; for(int i=0;i<ins;i++){ Receive(i); wynik+=GetInt(i); } cout<<wynik<<"\n"; } |