oj.uz

Submission #288670

# Submission time Handle Problem Language Result Execution time Memory
288670 2020-09-01T18:11:27 Z LordOfIran Senior Postmen (BOI14_postmen) C++17
100 / 100
 330 ms 47612 KB 
    #include <bits/stdc++.h> 
     
    using namespace std;
     
    #define rep(i , j , k) for (int i = j; i < (int)k; i++)
    #define pb push_back
    typedef vector<int> vi;
     
    constexpr int N = 5e5 + 10;
     
    int n, m, a, b;
     
    int ptr[N];
    bitset<N> mark, mark2;
     
    int shit, to[N << 1], pre[N << 1], last[N << 1], junk[N << 1];
     
    inline void addEdge(int a , int b) {
    	to[shit] = b; pre[shit] = last[a]; last[a] = shit++;
    	to[shit] = a; pre[shit] = last[b]; last[b] = shit++;	
    }
     
    int st[N], R;
    void dfs(int v) {
    	while (last[v] != -1) {
    		int id = last[v];
    		last[v] = pre[id];
    		if (!mark[id / 2]) {
    			mark[id / 2] = true;
    			dfs(to[id]);
    		}
    	}
    	if (mark2[v]) {
    		while (mark2[v]) {
    			printf("%d" , st[R]);
    			if (st[R] == v) printf("\n");
    			else printf(" ");
    			mark2[st[R]] = false;
    			R--;
    		}
    	} 
    	mark2[v] = true;
    	st[++R] = v;
     
    }
     
    int main() {
    	memset(last, -1, sizeof(last));
    	scanf("%d%d" , &n , &m);
    	rep(i , 0 , m) {
    		scanf("%d%d" , &a , &b);
    		addEdge(a , b);
    	}
     
    	dfs(1);
     
    	return 0;
    }

Compilation message

postmen.cpp: In function 'int main()':
postmen.cpp:49:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   49 |      scanf("%d%d" , &n , &m);
      |      ~~~~~^~~~~~~~~~~~~~~~~~
postmen.cpp:51:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   51 |       scanf("%d%d" , &a , &b);
      |       ~~~~~^~~~~~~~~~~~~~~~~~

Subtask #1
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4224 KB Output is correct
2 Correct 3 ms 4224 KB Output is correct
3 Correct 3 ms 4224 KB Output is correct
4 Correct 4 ms 4480 KB Output is correct
5 Correct 3 ms 4352 KB Output is correct
6 Correct 4 ms 4608 KB Output is correct
7 Correct 11 ms 5248 KB Output is correct
8 Correct 4 ms 4352 KB Output is correct
9 Correct 48 ms 10872 KB Output is correct
10 Correct 4 ms 4352 KB Output is correct
11 Correct 4 ms 4352 KB Output is correct
12 Correct 50 ms 10936 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4224 KB Output is correct
2 Correct 3 ms 4224 KB Output is correct
3 Correct 3 ms 4224 KB Output is correct
4 Correct 4 ms 4480 KB Output is correct
5 Correct 3 ms 4352 KB Output is correct
6 Correct 5 ms 4608 KB Output is correct
7 Correct 10 ms 5248 KB Output is correct
8 Correct 4 ms 4352 KB Output is correct
9 Correct 48 ms 11000 KB Output is correct
10 Correct 4 ms 4352 KB Output is correct
11 Correct 4 ms 4352 KB Output is correct
12 Correct 50 ms 11000 KB Output is correct
13 Correct 55 ms 11512 KB Output is correct
14 Correct 52 ms 8952 KB Output is correct
15 Correct 64 ms 11000 KB Output is correct
16 Correct 55 ms 11512 KB Output is correct
17 Correct 55 ms 6776 KB Output is correct
18 Correct 53 ms 10104 KB Output is correct

Subtask #3
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4224 KB Output is correct
2 Correct 3 ms 4224 KB Output is correct
3 Correct 3 ms 4224 KB Output is correct
4 Correct 4 ms 4480 KB Output is correct
5 Correct 3 ms 4352 KB Output is correct
6 Correct 5 ms 4608 KB Output is correct
7 Correct 9 ms 5248 KB Output is correct
8 Correct 4 ms 4352 KB Output is correct
9 Correct 46 ms 10872 KB Output is correct
10 Correct 4 ms 4352 KB Output is correct
11 Correct 4 ms 4352 KB Output is correct
12 Correct 51 ms 11000 KB Output is correct
13 Correct 54 ms 11640 KB Output is correct
14 Correct 54 ms 8952 KB Output is correct
15 Correct 50 ms 11000 KB Output is correct
16 Correct 54 ms 11512 KB Output is correct
17 Correct 53 ms 6776 KB Output is correct
18 Correct 55 ms 10104 KB Output is correct
19 Correct 320 ms 41208 KB Output is correct
20 Correct 304 ms 28840 KB Output is correct
21 Correct 296 ms 43256 KB Output is correct
22 Correct 320 ms 47612 KB Output is correct
23 Correct 227 ms 41208 KB Output is correct
24 Correct 330 ms 23800 KB Output is correct
25 Correct 325 ms 39928 KB Output is correct