oj.uz

Submission #95455

# Submission time Handle Problem Language Result Execution time Memory
95455 2019-02-01T09:42:32 Z mzhao Praktični (COCI18_prakticni) C++11
26 / 130
 147 ms 14836 KB 
#include <bits/stdc++.h>
using namespace std;

#ifdef DEBUG
#define D(x...) printf(x)
#else
#define D(x...)
#endif

#define x first
#define y second
#define MN 100100

int N, M;

struct End {
	int n, w, i;
};

vector<End> adj[MN];

int dep[MN];
bool vis[MN];
vector<int> st;

map<int, int> cnt;
vector<pair<int, int>> s;
set<int> t;

void dfs(int n, int d) {
	vis[n] = 1;
	dep[n] = d;
	for (End i : adj[n]) if (!vis[i.n]) {
		st.push_back(st.back() ^ i.w);
		dfs(i.n, d+1);
		st.pop_back();
	} else if (dep[i.n] < d) {
		int val = st.back() ^ st[dep[i.n]] ^ i.w;
		if (val) {
			s.push_back({val, i.i});
			t.insert(val);
			cnt[val]++;
		}
	}
}

int main() {
	scanf("%d%d", &N, &M);
	for (int i = 1, A, B, C; i <= M; i++) {
		scanf("%d%d%d", &A, &B, &C);
		adj[A].push_back({B, C, i});
		adj[B].push_back({A, C, i});
	}
	st.push_back(0);
	dfs(1, 0);
	sort(s.begin(), s.end());
	for (int i = 0; i < s.size(); i++) D("%d %d\n", s[i].x, s[i].y);
	D("ANS:\n\n");
	printf("%d", t.size());
	for (int i = 0; i < s.size(); i++) {
		if (!i || s[i].x != s[i-1].x) {
			printf("\n%d %d %d", s[i].x, cnt[s[i].x], s[i].y);
		} else {
			printf(" %d", s[i].y);
		}
	}
	printf("\n");
}

Compilation message

parkticni.cpp: In function 'int main()':
parkticni.cpp:57:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < s.size(); i++) D("%d %d\n", s[i].x, s[i].y);
                  ~~^~~~~~~~~~
parkticni.cpp:59:23: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::set<int>::size_type {aka long unsigned int}' [-Wformat=]
  printf("%d", t.size());
               ~~~~~~~~^
parkticni.cpp:60:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < s.size(); i++) {
                  ~~^~~~~~~~~~
parkticni.cpp:48:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &N, &M);
  ~~~~~^~~~~~~~~~~~~~~~
parkticni.cpp:50:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &A, &B, &C);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 7288 KB Output is correct
2 Correct 38 ms 7544 KB Output is correct
3 Correct 12 ms 3828 KB Output is correct
4 Correct 11 ms 3832 KB Output is correct
5 Correct 127 ms 12656 KB Output is correct
6 Correct 72 ms 11640 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 4728 KB Output is correct
2 Correct 18 ms 4856 KB Output is correct
3 Correct 23 ms 5596 KB Output is correct
4 Correct 31 ms 6164 KB Output is correct
5 Correct 90 ms 11376 KB Output is correct
6 Correct 45 ms 8040 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 53 ms 8312 KB Too many operations
2 Halted 0 ms 0 KB -

Subtask #4
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 84 ms 10784 KB Too many operations
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 59 ms 8824 KB Too many operations
2 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 85 ms 9468 KB Too many operations
2 Halted 0 ms 0 KB -

Subtask #7
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 95 ms 11228 KB Too many operations
2 Halted 0 ms 0 KB -

Subtask #8
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 147 ms 14836 KB Too many operations
2 Halted 0 ms 0 KB -

Subtask #9
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 28 ms 5368 KB Too many operations
2 Halted 0 ms 0 KB -

Subtask #10
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 115 ms 12132 KB Too many operations
2 Halted 0 ms 0 KB -