oj.uz

답안 #81931

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
81931 2018-10-27T22:55:29 Z Shtef Teoretičar (COCI18_teoreticar) C++14
0 / 130
 12000 ms 92380 KB 
#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
#include <cstring>

using namespace std;

typedef pair <int, int> pii;
#define x first
#define y second
#define mp make_pair

int l, r, m, sad, boja[1000005], vr[1000005];
vector <pii> edg;
vector <int> ms[200005];
bool bio[1000005];

void dfs(int x){
	while(!ms[x].empty()){
		int idx = ms[x].back();
		pii o = edg[idx];
		ms[x].pop_back();
		int y = (o.x == x ? o.y : o.x);
		if(bio[idx])
			continue;
		bio[idx] = 1;
		vr[idx] = sad;
		sad ^= 1;
		dfs(y);
	}
}

vector <int> solve(vector <pii> e){
	if(e.empty())
		return {};
	vector <int> lt, rt;
	//cout << e.size() << endl;
	for(int i = 0 ; i < e.size() ; ++i){
		//cout << e[i].x << ' ' << e[i].y << endl;
		int x = e[i].x, y = e[i].y;
		lt.push_back(x);
		rt.push_back(y);
	}
	//cout << endl;
	sort(lt.begin(), lt.end());
	sort(rt.begin(), rt.end());
	lt.resize(unique(lt.begin(), lt.end()) - lt.begin());
	rt.resize(unique(rt.begin(), rt.end()) - rt.begin());
	edg.clear();
	for(int i = 0 ; i <= l + r + 1 ; ++i){
		ms[i].clear();
	}
	for(int i = 0 ; i < e.size() ; ++i){
		int x = e[i].x, y = e[i].y;
		x = lower_bound(lt.begin(), lt.end(), x) - lt.begin();
		y = lower_bound(rt.begin(), rt.end(), y) - rt.begin();
		y += l + 1;
		edg.push_back(mp(x, y));
		ms[x].push_back(i);
		ms[y].push_back(i);
	}
	vector <int> tc;
	int maxi = 0;
	for(int i = 0 ; i <= l + r + 1 ; ++i){
		maxi = max(maxi, (int)ms[i].size());
		if(ms[i].size() & 1){
			tc.push_back(i);
		}
	}
	bool p = 1;
	for(int i = 0 ; i <= l + r + 1 ; ++i){
		p &= (ms[i].size() <= 1);
	}
	if(p){
		vector <int> ret;
		for(int i = 0 ; i < e.size() ; ++i){
			ret.push_back(1);
		}
		return ret;
	}
	int idx = e.size();
	for(int i = 0 ; i < tc.size() ; ++i){
		int x = tc[i];
		//cout << x << " : ";
		if(x <= l){
			edg.push_back(mp(x, l + r + 1));
			ms[x].push_back(idx);
			ms[l + r + 1].push_back(idx);
			idx++;
		}
		else{
			edg.push_back(mp(l, x));
			ms[l].push_back(idx);
			ms[x].push_back(idx);
			idx++;
		}
	}
	//cout << endl;
	if(ms[0].size() & 1){
		edg.push_back(mp(0, l + r + 1));
		ms[0].push_back(idx);
		ms[l + r + 1].push_back(idx);
		idx++;
	}
	memset(vr, -1, sizeof(vr));
	memset(bio, 0, sizeof(bio));
	for(int i = 0 ; i <= l + r + 1 ; ++i){
		if(!ms[i].empty()){
			dfs(i);
		}
	}
	vector <pii> lc, rc;
	vector <int> tvr;
	for(int i = 0 ; i < (int)e.size() ; ++i){
		tvr.push_back(vr[i]);
		if(!vr[i]){
			lc.push_back(e[i]);
		}
		else{
			rc.push_back(e[i]);
		}
	}
	vector <int> sl = solve(lc), sr = solve(rc);
	vector <int> ret;
	int br1 = 0, br2 = 0, val = *max_element(sl.begin(), sl.end());
	for(int i = 0 ; i < (int)e.size() ; ++i){
		if(!tvr[i]){
			ret.push_back(sl[br1++]);
		}
		else{
			ret.push_back(sr[br2++] + val);
		}
	}
	return ret;
}

int main ()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> l >> r >> m;
int br = 0;
for(int i = 0 ; i < m ; ++i){
	int x, y;
	cin >> x >> y;
	x--;
	y--;
	edg.push_back(mp(x, y));
}
vector <int> sol = solve(edg);
cout << *max_element(sol.begin(), sol.end()) << endl;
for(int i = 0 ; i < sol.size() ; ++i){
	cout << sol[i] << endl;
}

return 0;
}

Compilation message

teoreticar.cpp: In function 'std::vector<int> solve(std::vector<std::pair<int, int> >)':
teoreticar.cpp:39:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0 ; i < e.size() ; ++i){
                  ~~^~~~~~~~~~
teoreticar.cpp:54:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0 ; i < e.size() ; ++i){
                  ~~^~~~~~~~~~
teoreticar.cpp:77:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0 ; i < e.size() ; ++i){
                   ~~^~~~~~~~~~
teoreticar.cpp:83:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0 ; i < tc.size() ; ++i){
                  ~~^~~~~~~~~~~
teoreticar.cpp: In function 'int main()':
teoreticar.cpp:154:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 for(int i = 0 ; i < sol.size() ; ++i){
                 ~~^~~~~~~~~~~~
teoreticar.cpp:144:5: warning: unused variable 'br' [-Wunused-variable]
 int br = 0;
     ^~

Subtask #1
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 13 ms 9976 KB too many colors
2 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 18 ms 10108 KB too many colors
2 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 27 ms 10768 KB Output is correct
2 Incorrect 38 ms 10808 KB too many colors
3 Halted 0 ms 0 KB -

Subtask #4
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 112 ms 10812 KB too many colors
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1644 ms 53304 KB Output is correct
2 Execution timed out 12061 ms 82380 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1735 ms 82380 KB Output is correct
2 Correct 3133 ms 84412 KB Output is correct
3 Incorrect 4554 ms 92380 KB too many colors
4 Halted 0 ms 0 KB -

Subtask #7
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 12029 ms 92380 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3256 ms 92380 KB too many colors
2 Halted 0 ms 0 KB -

Subtask #9
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4259 ms 92380 KB too many colors
2 Halted 0 ms 0 KB -

Subtask #10
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4345 ms 92380 KB too many colors
2 Halted 0 ms 0 KB -