Submission #1041649

# Submission time Handle Problem Language Result Execution time Memory
1041649 2024-08-02T06:43:24 Z 김은성(#11000) Brought Down the Grading Server? (CEOI23_balance) C++17
0 / 100
3 ms 9052 KB
#include <bits/stdc++.h>
using namespace std;
int n, s, t, *a[100009];
vector<pair<int, int> > graph[100009];
int ans[100009];
int deg[100009];	//out - in;
int cur[100009];
bool ch[100009];
void findcycle(int v){
	for(int i = cur[v]; i<graph[v].size(); i++){
		if(i < cur[v])
			i = cur[v];
		if(i == graph[v].size())
			break;
		auto [idx, u] = graph[v][i];
		cur[v]++;
		if(ans[idx] != -1)
			continue;
		ans[idx] = v;
		deg[v]++;
		deg[u]--;
		findcycle(u);
	}
}
void findpath(int v){
	for(int i = 0; i<graph[v].size(); i++){
		auto [idx, u] = graph[v][i];
		if(ans[idx] != -1)
			continue;
		ans[idx] = v;
		deg[v]++;
		deg[u]--;
		if(ch[u] || graph[u].size()%2 == 0){
			findpath(u);
			break;
		}
		else{
			ch[u] = 1;
			break;
		}
	}
}
int main(){
	int i, j;
	scanf("%d %d %d", &n, &s, &t);
	assert(n <= 20);
	memset(ans, -1, sizeof(ans));
	for(i=0; i<n; i++){
		a[i] = (int*)malloc(s * sizeof(int));
		for(j=0; j<s; j++){
			scanf("%d", &a[i][j]);
		}
		graph[a[i][0]].push_back(make_pair(i, a[i][1]));
		graph[a[i][1]].push_back(make_pair(i, a[i][0]));
	}
	for(i=1; i<=t; i++){
		if(graph[i].size()%2 == 1 && !ch[i])
			findpath(i), ch[i]=1;
	}
	memset(cur, 0, sizeof(cur));
	for(i=1; i<=t; i++){
		findcycle(i);
	}
	for(i=1; i<=t; i++){
		assert(-1 <= deg[i] && deg[i] <= 1);
	}
	for(i=0; i<n; i++){
		printf("%d %d\n", ans[i], a[i][0] + a[i][1] - ans[i]);
	}
	return 0;
}

Compilation message

balance.cpp: In function 'void findcycle(int)':
balance.cpp:10:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   10 |  for(int i = cur[v]; i<graph[v].size(); i++){
      |                      ~^~~~~~~~~~~~~~~~
balance.cpp:13:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 |   if(i == graph[v].size())
      |      ~~^~~~~~~~~~~~~~~~~~
balance.cpp: In function 'void findpath(int)':
balance.cpp:26:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |  for(int i = 0; i<graph[v].size(); i++){
      |                 ~^~~~~~~~~~~~~~~~
balance.cpp: In function 'int main()':
balance.cpp:45:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |  scanf("%d %d %d", &n, &s, &t);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
balance.cpp:51:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |    scanf("%d", &a[i][j]);
      |    ~~~~~^~~~~~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Correct
2 Incorrect 1 ms 4444 KB Unexpected end of file - int32 expected
3 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Correct
2 Correct 1 ms 4444 KB Correct
3 Runtime error 3 ms 9052 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 8792 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 8792 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Correct
2 Correct 1 ms 4444 KB Correct
3 Runtime error 3 ms 9052 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 4444 KB Unexpected end of file - int32 expected
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 4444 KB Unexpected end of file - int32 expected
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 4444 KB Unexpected end of file - int32 expected
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 8792 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 8792 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Correct
2 Incorrect 1 ms 4444 KB Unexpected end of file - int32 expected
3 Halted 0 ms 0 KB -