제출 #419005

#제출 시각아이디문제언어결과실행 시간메모리
419005RambaXGorillaOne-Way Streets (CEOI17_oneway)C++17
0 / 100
7 ms9164 KiB
#include<cstdio> #include<cstdlib> #include<algorithm> #include<vector> #include<map> #include<utility> using namespace std; int N, M, P; pair <int,int> roads[100010]; pair <int,int> save[100010]; int imps[100010][3]; int dfsCnt = 0; bool vis[100010]; int pows[20]; int dfsNums[100010]; int dfsLows[100010]; int dfsPars[100010]; int cons[100010]; int treePars[100010]; int dirs[100010]; char trans[] = {'L', 'B', 'R'}; vector <int> adjGraph[100010]; vector <int> adjTree[100010]; vector <int> adjCycles[100010]; map < pair <int,int>, int> goBack; map < pair <int,int>, bool> bridges; void getBridges(int u){ dfsNums[u] = dfsLows[u] = dfsCnt++; for(int i = 0;i < adjGraph[u].size();i++){ int v = adjGraph[u][i]; if(dfsNums[v] == -1){ dfsPars[v] = u; getBridges(v); if(dfsLows[v] > dfsNums[u]){ bridges[make_pair(min(u, v), max(u, v))] = true; } dfsLows[u] = min(dfsLows[u], dfsLows[v]); } else if(dfsPars[u] != v || goBack[make_pair(min(u, v), max(u, v))] > 1){ dfsLows[u] = min(dfsLows[u], dfsNums[v]); } } } void getCycles(int u, int r){ cons[u] = r; for(int i = 0;i < adjCycles[u].size();i++){ int v = adjCycles[u][i]; if(cons[v] == -1){ getCycles(v, r); } } } void getTreePars(int u){ for(int i = 0;i < adjTree[u].size();i++){ int v = adjTree[u][i]; if(treePars[v] == -1){ treePars[v] = u; getTreePars(v); } } } void addTreeDirs(int u){ vis[u] = true; for(int i = 0;i < adjTree[u].size();i++){ int v = adjTree[u][i]; if(!vis[v]){ addTreeDirs(v); dirs[u] += dirs[v]; } } } int main(){ scanf("%d%d",&N,&M); for(int i = 0;i < M;i++){ scanf("%d%d",&roads[i].first,&roads[i].second); save[i] = roads[i]; if(roads[i].first > roads[i].second){ swap(roads[i].first, roads[i].second); } else if(roads[i].first == roads[i].second){ continue; } goBack[roads[i]] += 1; if(goBack[roads[i]] == 1){ adjGraph[roads[i].first].push_back(roads[i].second); adjGraph[roads[i].second].push_back(roads[i].first); } } scanf("%d",&P); for(int i = 0;i < P;i++){ scanf("%d%d",&imps[i][0],&imps[i][1]); } int length = 1; for(int i = 0;i < 20;i++){ pows[i] = length; length *= 2; } for(int i = 0;i < 100010;i++){ dfsNums[i] = -1; cons[i] = -1; treePars[i] = -1; dirs[i] = 0; vis[i] = false; } for(int i = 1;i < N + 1;i++){ if(dfsNums[i] == -1){ getBridges(i); } } for(int i = 0;i < M;i++){ if(!bridges[roads[i]]){ adjCycles[roads[i].first].push_back(roads[i].second); adjCycles[roads[i].second].push_back(roads[i].first); } } int cnt = 0; for(int i = 1;i < N + 1;i++){ if(cons[i] == -1){ cnt += 1; getCycles(i, cnt); } } for(int i = 0;i < M;i++){ if(bridges[roads[i]]){ adjTree[cons[roads[i].first]].push_back(cons[roads[i].second]); adjTree[cons[roads[i].second]].push_back(cons[roads[i].first]); } } for(int i = 1;i < cnt + 1;i++){ if(treePars[i] == -1){ treePars[i] = 0; getTreePars(i); } } for(int i = 0;i < P;i++){ dirs[cons[imps[i][0]]] = 1; dirs[cons[imps[i][1]]] = -1; } for(int i = 1;i < cnt + 1;i++){ if(!vis[i]){ addTreeDirs(i); } } for(int i = 0;i < M;i++){ int u = save[i].first; int v = save[i].second; int uT = cons[u]; int vT = cons[v]; if(uT == vT){ printf("B"); continue; } int d; if(treePars[uT] == vT){ d = dirs[uT]; } else{ d = dirs[vT] * -1; } if(d != 0){ d /= abs(d); } printf("%c",trans[d + 1]); } }

컴파일 시 표준 에러 (stderr) 메시지

oneway.cpp: In function 'void getBridges(int)':
oneway.cpp:29:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |     for(int i = 0;i < adjGraph[u].size();i++){
      |                   ~~^~~~~~~~~~~~~~~~~~~~
oneway.cpp: In function 'void getCycles(int, int)':
oneway.cpp:46:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |     for(int i = 0;i < adjCycles[u].size();i++){
      |                   ~~^~~~~~~~~~~~~~~~~~~~~
oneway.cpp: In function 'void getTreePars(int)':
oneway.cpp:54:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |     for(int i = 0;i < adjTree[u].size();i++){
      |                   ~~^~~~~~~~~~~~~~~~~~~
oneway.cpp: In function 'void addTreeDirs(int)':
oneway.cpp:64:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |     for(int i = 0;i < adjTree[u].size();i++){
      |                   ~~^~~~~~~~~~~~~~~~~~~
oneway.cpp: In function 'int main()':
oneway.cpp:73:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   73 |     scanf("%d%d",&N,&M);
      |     ~~~~~^~~~~~~~~~~~~~
oneway.cpp:75:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   75 |         scanf("%d%d",&roads[i].first,&roads[i].second);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
oneway.cpp:89:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   89 |     scanf("%d",&P);
      |     ~~~~~^~~~~~~~~
oneway.cpp:91:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   91 |         scanf("%d%d",&imps[i][0],&imps[i][1]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...