oj.uz

Submission #197529

# Submission time Handle Problem Language Result Execution time Memory
197529 2020-01-21T14:42:47 Z dndhk Senior Postmen (BOI14_postmen) C++14
55 / 100
 500 ms 67488 KB 
#include <bits/stdc++.h>

#define pb push_back

using namespace std;

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

const int MAX_N = 500000;

int N, M;
vector<int> gp[MAX_N+1];
bool chk[MAX_N+1];
pii p[MAX_N+1];
vector<int> v;
vector<int> nxt[MAX_N+1];
bool vst[MAX_N+1];
vector<int> vt;

int main(){
	scanf("%d%d", &N, &M);
	for(int i=1; i<=M; i++){
		int a, b; scanf("%d%d", &a, &b);
		gp[a].pb(i);
		gp[b].pb(i);
		p[i] = {a, b};
	}
	for(int i=1; i<=N; i++){
		for(int j=0; j<gp[i].size(); j+=2){
			nxt[gp[i][j]].pb(gp[i][j+1]);
			nxt[gp[i][j+1]].pb(gp[i][j]);
		}
	}
	for(int i=1; i<=M; i++){
		if(!chk[i]){
			chk[i] = true;
			chk[nxt[i][0]] = true;
			v.pb(nxt[i][0]);
			v.pb(i);
			int n = nxt[i][1];
			while(1){
				chk[n] = true;
				v.pb(n);
				if(chk[nxt[n][0]] && chk[nxt[n][1]]){
					break;
				}
				if(chk[nxt[n][0]]){
					n = nxt[n][1];
				}else{
					n = nxt[n][0];
				}
			}
			int x;
			if(p[v.back()].first==p[v[0]].first || p[v.back()].first==p[v[0]].second){
				x = p[v.back()].first;
			}else{
				x = p[v.back()].second;
			}
			while(!v.empty()){
				x = p[v.back()].first+p[v.back()].second-x;
				if(vst[x]){
					while(vt.back()!=x){
						vst[vt.back()] = false;
						printf("%d ", vt.back());
						vt.pop_back();
					}
					printf("%d\n", x);
				}else{
					vst[x] = true;
					vt.pb(x);
				}
				v.pop_back();
			}
			if(!vt.empty()){
				while(!vt.empty()){
					vst[vt.back()] = false;
					printf("%d ", vt.back()); 
					vt.pop_back();
				}printf("\n");
			}
		}
	}
	return 0;
}

Compilation message

postmen.cpp: In function 'int main()':
postmen.cpp:31:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0; j<gp[i].size(); j+=2){
                ~^~~~~~~~~~~~~
postmen.cpp:23:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &N, &M);
  ~~~~~^~~~~~~~~~~~~~~~
postmen.cpp:25:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int a, b; scanf("%d%d", &a, &b);
             ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 23808 KB Output is correct
2 Correct 20 ms 23808 KB Output is correct
3 Correct 20 ms 23784 KB Output is correct
4 Correct 24 ms 24100 KB Output is correct
5 Correct 27 ms 23928 KB Output is correct
6 Correct 28 ms 24084 KB Output is correct
7 Correct 28 ms 24704 KB Output is correct
8 Correct 19 ms 23936 KB Output is correct
9 Correct 110 ms 29436 KB Output is correct
10 Correct 22 ms 24020 KB Output is correct
11 Correct 21 ms 24064 KB Output is correct
12 Correct 115 ms 29644 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 23808 KB Output is correct
2 Correct 21 ms 23808 KB Output is correct
3 Correct 26 ms 23808 KB Output is correct
4 Correct 24 ms 24040 KB Output is correct
5 Correct 21 ms 23936 KB Output is correct
6 Correct 24 ms 24036 KB Output is correct
7 Correct 26 ms 24704 KB Output is correct
8 Correct 22 ms 24044 KB Output is correct
9 Correct 106 ms 29520 KB Output is correct
10 Correct 25 ms 24040 KB Output is correct
11 Correct 20 ms 24064 KB Output is correct
12 Correct 108 ms 29560 KB Output is correct
13 Correct 127 ms 32624 KB Output is correct
14 Correct 160 ms 30912 KB Output is correct
15 Correct 127 ms 31220 KB Output is correct
16 Correct 137 ms 32672 KB Output is correct
17 Correct 155 ms 30840 KB Output is correct
18 Correct 146 ms 31344 KB Output is correct

Subtask #3
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 23808 KB Output is correct
2 Correct 23 ms 23808 KB Output is correct
3 Correct 23 ms 23808 KB Output is correct
4 Correct 23 ms 24100 KB Output is correct
5 Correct 28 ms 23936 KB Output is correct
6 Correct 21 ms 24064 KB Output is correct
7 Correct 31 ms 24704 KB Output is correct
8 Correct 21 ms 24064 KB Output is correct
9 Correct 110 ms 29432 KB Output is correct
10 Correct 24 ms 24064 KB Output is correct
11 Correct 19 ms 24064 KB Output is correct
12 Correct 121 ms 29688 KB Output is correct
13 Correct 135 ms 32624 KB Output is correct
14 Correct 148 ms 31032 KB Output is correct
15 Correct 120 ms 31172 KB Output is correct
16 Correct 127 ms 32624 KB Output is correct
17 Correct 149 ms 30840 KB Output is correct
18 Correct 126 ms 31400 KB Output is correct
19 Execution timed out 793 ms 67488 KB Time limit exceeded
20 Halted 0 ms 0 KB -