제출 #82898

#제출 시각아이디문제언어결과실행 시간메모리
82898georgerapeanuTeoretičar (COCI18_teoreticar)C++11
0 / 130
4754 ms62872 KiB
#include <cstdio> #include <algorithm> #include <vector> using namespace std; const int NMAX = 2e5; const int MMAX = 5e5; vector< pair<int,int> > graph[NMAX + 5]; int gr[NMAX + 5]; int ans[MMAX + 5]; vector<pair<pair<int,int>,int> > euler; bool used[MMAX + 5]; void get_euler(int node,bool dump){ if(dump){ euler.clear(); } vector<pair<int,pair<pair<int,int>,int> > > st; st.push_back({node,{{0,0},0}}); while(!st.empty()){ node = st.back().first; pair<pair<int,int>,int> edge = st.back().second; while(!graph[node].empty() && used[graph[node].back().second]){ graph[node].pop_back(); } if(graph[node].empty()){ euler.push_back(edge); st.pop_back(); } else{ int it = graph[node].back().first; int id = graph[node].back().second; graph[node].pop_back(); used[id] = true; st.push_back(make_pair(it,make_pair(make_pair(node,it),id))); } } } void solve(vector< pair<pair<int,int>,int> > &edges,int &last_cul){ int ma = 0; for(auto it:edges){ gr[it.first.first]++; gr[it.first.second]++; graph[it.first.first].push_back({it.first.second,it.second}); graph[it.first.second].push_back({it.first.first,it.second}); ma = max(ma,gr[it.first.first]); ma = max(ma,gr[it.first.second]); } if(ma <= 1){ last_cul++; for(auto it:edges){ ans[it.second] = last_cul; gr[it.first.first] = 0; gr[it.first.second] = 0; graph[it.first.first].clear(); graph[it.first.second].clear(); } return ; } int fst_virtual = NMAX + 1; int snd_virtual = NMAX + 2; for(auto it:edges){ if(gr[it.first.first] % 2 == 1){ gr[it.first.first]++; gr[snd_virtual]++; graph[it.first.first].push_back({snd_virtual,0}); graph[snd_virtual].push_back({it.first.first,0}); } if(gr[it.first.second] % 2 == 1){ gr[it.first.second]++; gr[fst_virtual]++; graph[it.first.second].push_back({fst_virtual,0}); graph[fst_virtual].push_back({it.first.second,0}); } } used[0] = false; for(auto it:edges){ used[it.second] = false; } get_euler(fst_virtual,1); get_euler(snd_virtual,0); for(auto it:edges){ get_euler(it.first.first,0); get_euler(it.first.second,0); } vector<pair<pair<int,int>,int> > x[2]; int l = 0; for(int i = 0;i < (int)euler.size();i++){ if(!euler[i].second){ continue; } x[l].push_back(euler[i]); l ^= 1; } for(auto it:edges){ gr[it.first.first] = 0; gr[it.first.second] = 0; graph[it.first.second].clear(); graph[it.first.first].clear(); } graph[fst_virtual].clear();gr[fst_virtual] = 0; graph[snd_virtual].clear();gr[snd_virtual] = 0; solve(x[0],last_cul); solve(x[1],last_cul); } int main(){ int l,r,m; scanf("%d %d %d",&l,&r,&m); vector<pair<pair<int,int>,int> > edges; for(int i = 1;i <= m;i++){ int x,y; scanf("%d %d",&x,&y); y += l; edges.push_back({{x,y},i}); } int last_cul = 0; solve(edges,last_cul); printf("%d\n",last_cul); for(int i = 1;i <= m;i++){ printf("%d\n",ans[i]); } return 0; }

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

teoreticar.cpp: In function 'int main()':
teoreticar.cpp:139:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d",&l,&r,&m);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~
teoreticar.cpp:145:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&x,&y);
   ~~~~~^~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...