oj.uz

Submission #348516

# Submission time Handle Problem Language Result Execution time Memory
348516 2021-01-15T05:55:21 Z arnold518 Information (CEOI08_information) C++14
58 / 100
 435 ms 20332 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 2000;
const int MAXM = 1e6;

mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

int N, M;
pii E[MAXM+10];
vector<pii> adj[MAXN+10];

int chk[MAXM+10];
bool vis[MAXN+10];

void dfs(int now, int col)
{
	vis[now]=true;
	for(pii nxt : adj[now])
	{
		if(chk[nxt.second]) continue;
		if(vis[nxt.first]) continue;
		chk[nxt.second]=col;
		dfs(nxt.first, col);
	}
}

int main()
{
	scanf("%d%d", &N, &M);
	for(int i=1; i<=M; i++)
	{
		int u, v;
		scanf("%d%d", &u, &v);
		E[i]={u, v};
		adj[u].push_back({v, i});
	}

	for(int k=1; k<=10; k++)
	{
		for(int i=1; i<=N; i++) shuffle(adj[i].begin(), adj[i].end(), rng);
		memset(vis, 0, sizeof(vis));
		dfs(1, 1);
		memset(vis, 0, sizeof(vis));
		dfs(1, 2);

		vector<int> V1, V2;
		for(int i=1; i<=M; i++)
		{
			if(chk[i]==1) V1.push_back(i);
			else if(chk[i]==2) V2.push_back(i);
		}
		if(V1.size()!=N-1 || V2.size()!=N-1) continue;
		for(auto it : V1) printf("%d ", it); printf("\n");
		for(auto it : V2) printf("%d ", it); printf("\n");
		return 0;
	}
	printf("NONE\n");
}

Compilation message

information.cpp: In function 'int main()':
information.cpp:57:15: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   57 |   if(V1.size()!=N-1 || V2.size()!=N-1) continue;
      |      ~~~~~~~~~^~~~~
information.cpp:57:33: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   57 |   if(V1.size()!=N-1 || V2.size()!=N-1) continue;
      |                        ~~~~~~~~~^~~~~
information.cpp:58:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   58 |   for(auto it : V1) printf("%d ", it); printf("\n");
      |   ^~~
information.cpp:58:40: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   58 |   for(auto it : V1) printf("%d ", it); printf("\n");
      |                                        ^~~~~~
information.cpp:59:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   59 |   for(auto it : V2) printf("%d ", it); printf("\n");
      |   ^~~
information.cpp:59:40: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   59 |   for(auto it : V2) printf("%d ", it); printf("\n");
      |                                        ^~~~~~
information.cpp:34:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   34 |  scanf("%d%d", &N, &M);
      |  ~~~~~^~~~~~~~~~~~~~~~
information.cpp:38:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   38 |   scanf("%d%d", &u, &v);
      |   ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 364 KB Output isn't correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct

Subtask #4
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 364 KB Output isn't correct

Subtask #5
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct

Subtask #6
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct

Subtask #7
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 364 KB Output isn't correct

Subtask #8
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct

Subtask #9
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 492 KB Output is correct

Subtask #10
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 620 KB Output is correct

Subtask #11
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 492 KB Output isn't correct

Subtask #12
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct

Subtask #13
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct

Subtask #14
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 364 KB Output isn't correct

Subtask #15
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 2668 KB Output is correct

Subtask #16
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 89 ms 4560 KB Output isn't correct

Subtask #17
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 44 ms 2668 KB Output isn't correct

Subtask #18
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 1 ms 364 KB Output is correct

Subtask #19
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 492 KB Output is correct

Subtask #20
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 492 KB Output isn't correct

Subtask #21
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 235 ms 20204 KB Output is correct

Subtask #22
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 220 ms 19436 KB Output is correct

Subtask #23
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 435 ms 20332 KB Output isn't correct

Subtask #24
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 492 KB Output isn't correct
2 Halted 0 ms 0 KB -