Submission #169522

#TimeUsernameProblemLanguageResultExecution timeMemory
169522Ruxandra985One-Way Streets (CEOI17_oneway)C++14
0 / 100
12 ms10488 KiB
#include <bits/stdc++.h> #define DIMN 100010 using namespace std; int low[DIMN],lvl[DIMN] , f[DIMN] , d[DIMN] , l[DIMN] , up[DIMN]; int poz[DIMN]; int lnt = 0; map <pair <int,int> , int> mc , nr_mch; pair <int,int> muchie[DIMN]; stack <int > st; vector <int> v[DIMN] , w[DIMN] , dfs_tree[DIMN] , aint[DIMN]; int x; void precalc (int nod){ int i,vecin; d[nod]=1; f[nod]=1; for (i=0;i<v[nod].size();i++){ vecin=v[nod][i]; if (!f[vecin]){ lvl[vecin]=1+lvl[nod]; dfs_tree[nod].push_back(vecin); precalc (vecin); d[nod]+=d[vecin]; } } } void dfs_lant(int nod,int tata){ int i,vecin,ok=0,maxi,fiu; f[nod] = 1; //if (nod == 54) // printf ("a"); maxi=0; fiu=0; for (i=0;i<dfs_tree[nod].size();i++){ vecin=dfs_tree[nod][i]; if (vecin != tata){ ok=1; dfs_lant(vecin,nod); if (d[vecin]>maxi){ maxi=d[vecin]; fiu=vecin; } } } if (!ok){ /// frunza lnt++; l[nod]=lnt; /// lantul din care apartine w[lnt].push_back(nod); }else { /// unim cu poz w[l[fiu]].push_back(nod); l[nod]=l[fiu]; for (i=0;i<dfs_tree[nod].size();i++){ vecin=dfs_tree[nod][i]; if (vecin!=tata && vecin!=fiu) up[l[vecin]]=nod; /// din lantul vecinului trecem in lantul nodului } } } void dfs_biconexe (int nod,int tt){ int i,vecin , nr = 0; low[nod]=lvl[nod]; st.push(nod); for (i=0;i<v[nod].size();i++){ vecin=v[nod][i]; if (vecin==tt) continue; if (lvl[vecin]==0){ lvl[vecin]=1+lvl[nod]; dfs_biconexe(vecin,nod); low[nod]=min(low[nod],low[vecin]); if (low[vecin]>=lvl[nod]){ /// nod e un nod critic //mc[make_pair(nod,vecin)] = 1; nr = 1; do{ x=st.top(); st.pop(); nr++; } while (x!=vecin); if (nr == 2){ mc[make_pair(nod,vecin)] = 1; //printf ("%d %d\n" , nod, vecin); } /// am scos din stiva muchiile care sunt in subarborele nod->vecin } } else low[nod]=min(low[nod],lvl[vecin]); } } void update_aint (int lant , int nod , int st , int dr , int l , int r , int val){ int mid = (st + dr)/2; //if ( l == 0 && r == 0 ) // printf ("%d %d\n",st,dr); if (l <= st && dr <= r){ aint[lant][nod] = val; /// tot intervalul ala are aceeasi valoare (1 sau -1) return; } if (l <= mid) update_aint (lant , 2*nod , st , mid , l , r, val); if (mid+1 <= r) update_aint (lant , 2*nod+1 , mid+1 , dr , l , r, val); } void update (int x , int y){ // printf ("%d %d\n" , x , y ); if (l[x]!=l[y]){ /// avansam if (lvl[up[l[x]]]>lvl[up[l[y]]]){ update(up[l[x]] , y); update_aint( l[x] , 1 , 0 , w[l[x]].size()-1 , 0 , poz[x] , 1); } else { update ( x , up[l[y]]); update_aint(l[y],1,0,w[l[y]].size()-1,0,poz[y] , -1); } } else { if (lvl[x] < lvl[y]) /// x e lca ul , te duci in jos , pui -1 update_aint(l[x],1,0,w[l[x]].size()-1,min(poz[y] , poz[x]),max(poz[y] , poz[x]) , -1); else update_aint(l[x],1,0,w[l[x]].size()-1,min(poz[y] , poz[x]),max(poz[y] , poz[x]) , 1); } } int query_aint (int lant,int nod,int st,int dr,int px){ int mid; if (aint[lant][nod] !=0 || st == dr) return aint[lant][nod]; mid=(st+dr)/2; if (px<=mid) return query_aint(lant,2*nod,st,mid,px); else return query_aint(lant,2*nod+1,mid+1,dr,px); } int main() { FILE *fin = stdin; FILE *fout = stdout; int n, m , i , x , y , p , vecin , nod , sol; pair <int,int> z; fscanf (fin,"%d%d",&n,&m); for (i=1;i<=m;i++){ fscanf (fin,"%d%d",&x,&y); v[x].push_back(y); v[y].push_back(x); nr_mch[make_pair(x , y)]++; nr_mch[make_pair(y , x)]++; muchie[i] = make_pair(x , y); } for (i=1;i<=n;i++){ if (!lvl[i]){ lvl[i] = 1; dfs_biconexe ( i, 0 ); } } /// vreau sa gasesc noduri critice /// daca un drum intre X Y trece printr o mch critica ins ca /// toate drumurile intre X Y trec pin acea muchie => /// muchia aia are sens prestabilit for (i=1;i<=n;i++){ if (!f[i]) precalc(i); } memset (f , 0 , sizeof ( f )); for (i=1;i<=n;i++){ if (!f[i]) dfs_lant(i , 0); } /// fiecare nod al catelea e for (i=1;i<=lnt;i++){ reverse(w[i].begin(),w[i].end()); p=0; for (vector <int> :: iterator j=w[i].begin();j!=w[i].end();j++){ /// pozitia lui din lantul curent vecin=*j; poz[vecin]=p; p++; } } /// folosesti aint for (i=1;i<=lnt;i++) aint[i].resize(w[i].size()*5); /// ai precalculat pentru heavy /// nu imi mai trb lca ul fscanf (fin,"%d",&p); for (i=1;i<=p;i++){ fscanf (fin,"%d%d",&x,&y); /// update pe lant x , z cu 1 = RIGHT /// update pe lant y , z cu -1 = LEFT update (x , y); } /// am facut updateurile , e momentul sa fac queryurile for (i=1;i<=m;i++){ if ( ( mc[muchie[i]] || mc[make_pair(muchie[i].second , muchie[i].first)] ) && nr_mch[muchie[i]] == 1 && muchie[i].first != muchie[i].second){ /// e muchie critica , trebuie sa vedem ce valoare are if (mc[muchie[i]]) nod = muchie[i].second; else nod = muchie[i].first; sol = query_aint (l[nod] , 1 , 0 , w[l[nod]].size() - 1 , poz[nod]); if (sol == 0) fprintf (fout,"B"); else if (sol == -1){ if (nod == muchie[i].first) fprintf (fout,"L"); else fprintf (fout,"R"); } else { if (nod == muchie[i].first) fprintf (fout,"R"); else fprintf (fout,"L"); } } else fprintf (fout,"B"); } return 0; }

Compilation message (stderr)

oneway.cpp: In function 'void precalc(int)':
oneway.cpp:16:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i=0;i<v[nod].size();i++){
              ~^~~~~~~~~~~~~~
oneway.cpp: In function 'void dfs_lant(int, int)':
oneway.cpp:35:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i=0;i<dfs_tree[nod].size();i++){
              ~^~~~~~~~~~~~~~~~~~~~~
oneway.cpp:53:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (i=0;i<dfs_tree[nod].size();i++){
                  ~^~~~~~~~~~~~~~~~~~~~~
oneway.cpp: In function 'void dfs_biconexe(int, int)':
oneway.cpp:65:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i=0;i<v[nod].size();i++){
              ~^~~~~~~~~~~~~~
oneway.cpp: In function 'int main()':
oneway.cpp:152:12: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     fscanf (fin,"%d%d",&n,&m);
     ~~~~~~~^~~~~~~~~~~~~~~~~~
oneway.cpp:154:16: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         fscanf (fin,"%d%d",&x,&y);
         ~~~~~~~^~~~~~~~~~~~~~~~~~
oneway.cpp:204:12: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     fscanf (fin,"%d",&p);
     ~~~~~~~^~~~~~~~~~~~~
oneway.cpp:206:16: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         fscanf (fin,"%d%d",&x,&y);
         ~~~~~~~^~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...