제출 #476966

#제출 시각아이디문제언어결과실행 시간메모리
476966AdamGSTeoretičar (COCI18_teoreticar)C++14
52 / 130
6356 ms147716 KiB
#include<bits/stdc++.h> using namespace std; typedef long double ld; #define int long long #define rep(a, b) for(int a = 0; a < (b); ++a) #define st first #define nd second #define pb push_back #define all(a) a.begin(), a.end() const int LIM=5e5+7; vector<pair<int,int>>V[LIM]; vector<int>cykl; pair<int,int>T[LIM]; int ans[LIM], li[LIM], odw[LIM], ile[LIM], l, r, m; bool ok(vector<int>kraw) { if(kraw.size()==0) return true; vector<int>wierz; for(auto i : kraw) { wierz.pb(T[i].st); wierz.pb(T[i].nd); } sort(all(wierz)); rep(i, wierz.size()-1) if(wierz[i]==wierz[i+1]) return false; return true; } void DFS(int x) { while(li[x]<V[x].size()) { int a=V[x][li[x]].st, b=V[x][li[x]].nd; ++li[x]; if(odw[b]) continue; odw[b]=1; DFS(a); cykl.pb(b); } } void dc(vector<int>kraw, int x) { if(ok(kraw)) return; vector<int>P, wierz, lewo, prawo; V[l+r].clear(); V[l+r+1].clear(); ile[l+r]=ile[l+r+1]=li[l+r]=li[l+r+1]=0; for(auto i : kraw) { V[T[i].st].clear(); V[T[i].nd].clear(); li[T[i].st]=ile[T[i].st]=0; li[T[i].nd]=ile[T[i].nd]=0; odw[i]=0; P.pb(T[i].st); P.pb(T[i].nd); } for(auto i : kraw) { V[T[i].st].pb({T[i].nd, i}); V[T[i].nd].pb({T[i].st, i}); ++ile[T[i].st]; ++ile[T[i].nd]; } sort(all(P)); wierz.pb(P[0]); rep(i, P.size()-1) if(P[i]!=P[i+1]) wierz.pb(P[i+1]); for(auto i : wierz) if(ile[i]%2==1) { if(i<l) lewo.pb(i); else prawo.pb(i); } int akt=m; rep(i, lewo.size()) { V[lewo[i]].pb({l+r, akt}); V[l+r].pb({lewo[i], akt}); ++akt; } rep(i, prawo.size()) { V[prawo[i]].pb({l+r+1, akt}); V[l+r+1].pb({prawo[i], akt}); ++akt; } if(V[l+r].size()%2==1) { V[l+r].pb({l+r+1, akt}); V[l+r+1].pb({l+r, akt}); ++akt; } if(lewo.size()%2==1) { V[lewo.back()].pb({prawo.back(), m}); V[prawo.back()].pb({lewo.back(), m}); lewo.pop_back(); prawo.pop_back(); ++akt; } for(int i=m; i<akt; ++i) odw[i]=0; vector<int>V1, V2; for(auto i : wierz) { cykl.clear(); DFS(i); rep(j, cykl.size()) if(cykl[j]<m) { if(j%2==0) V1.pb(cykl[j]); else V2.pb(cykl[j]); } } for(auto i : V1) ans[i]+=x; dc(V1, 2*x); dc(V2, 2*x); } int32_t main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> l >> r >> m; vector<int>kraw; rep(i, m) { cin >> T[i].st >> T[i].nd; --T[i].st; --T[i].nd; T[i].nd+=l; kraw.pb(i); } dc(kraw, 1); map<int,int>mp; vector<int>skal; rep(i, m) skal.pb(ans[i]); sort(all(skal)); int akt=0; for(auto i : skal) if(!mp[i]) { ++akt; mp[i]=akt; } cout << akt << '\n'; rep(i, m) cout << mp[ans[i]] << '\n'; }

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

teoreticar.cpp: In function 'bool ok(std::vector<long long int>)':
teoreticar.cpp:5:36: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    5 | #define rep(a, b) for(int a = 0; a < (b); ++a)
      |                                    ^
teoreticar.cpp:23:2: note: in expansion of macro 'rep'
   23 |  rep(i, wierz.size()-1) if(wierz[i]==wierz[i+1]) return false;
      |  ^~~
teoreticar.cpp: In function 'void DFS(long long int)':
teoreticar.cpp:27:13: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |  while(li[x]<V[x].size()) {
      |        ~~~~~^~~~~~~~~~~~
teoreticar.cpp: In function 'void dc(std::vector<long long int>, long long int)':
teoreticar.cpp:5:36: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    5 | #define rep(a, b) for(int a = 0; a < (b); ++a)
      |                                    ^
teoreticar.cpp:59:2: note: in expansion of macro 'rep'
   59 |  rep(i, P.size()-1) if(P[i]!=P[i+1]) wierz.pb(P[i+1]);
      |  ^~~
teoreticar.cpp:5:36: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    5 | #define rep(a, b) for(int a = 0; a < (b); ++a)
      |                                    ^
teoreticar.cpp:65:2: note: in expansion of macro 'rep'
   65 |  rep(i, lewo.size()) {
      |  ^~~
teoreticar.cpp:5:36: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    5 | #define rep(a, b) for(int a = 0; a < (b); ++a)
      |                                    ^
teoreticar.cpp:70:2: note: in expansion of macro 'rep'
   70 |  rep(i, prawo.size()) {
      |  ^~~
teoreticar.cpp:5:36: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    5 | #define rep(a, b) for(int a = 0; a < (b); ++a)
      |                                    ^
teoreticar.cpp:92:3: note: in expansion of macro 'rep'
   92 |   rep(j, cykl.size()) if(cykl[j]<m) {
      |   ^~~
#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...