oj.uz

답안 #197530

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
197530 2020-01-21T14:55:05 Z dndhk 어르신 집배원 (BOI14_postmen) C++14
55 / 100
 500 ms 67416 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;
			}
			vt.pb(x);
			vst[x] = true;
			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();
			}
			while(!vt.empty()){
				vst[vt.back()] = false;
				vt.pop_back();
			}
		}
	}
	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

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 23808 KB Output is correct
2 Correct 19 ms 23808 KB Output is correct
3 Correct 19 ms 23808 KB Output is correct
4 Correct 21 ms 24064 KB Output is correct
5 Correct 19 ms 23844 KB Output is correct
6 Correct 31 ms 24064 KB Output is correct
7 Correct 30 ms 24704 KB Output is correct
8 Correct 20 ms 23936 KB Output is correct
9 Correct 118 ms 29384 KB Output is correct
10 Correct 30 ms 24040 KB Output is correct
11 Correct 22 ms 24064 KB Output is correct
12 Correct 109 ms 29560 KB Output is correct

Subtask #2
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 23808 KB Output is correct
2 Correct 17 ms 23808 KB Output is correct
3 Correct 18 ms 23808 KB Output is correct
4 Correct 26 ms 24064 KB Output is correct
5 Correct 19 ms 23936 KB Output is correct
6 Correct 21 ms 24064 KB Output is correct
7 Correct 33 ms 24752 KB Output is correct
8 Correct 40 ms 23928 KB Output is correct
9 Correct 100 ms 29560 KB Output is correct
10 Correct 19 ms 24064 KB Output is correct
11 Correct 22 ms 24096 KB Output is correct
12 Correct 128 ms 29628 KB Output is correct
13 Correct 151 ms 32624 KB Output is correct
14 Correct 131 ms 30840 KB Output is correct
15 Correct 155 ms 31220 KB Output is correct
16 Correct 128 ms 32536 KB Output is correct
17 Correct 145 ms 30836 KB Output is correct
18 Correct 131 ms 31452 KB Output is correct

Subtask #3
0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 22 ms 23808 KB Output is correct
2 Correct 22 ms 23780 KB Output is correct
3 Correct 19 ms 23808 KB Output is correct
4 Correct 20 ms 24064 KB Output is correct
5 Correct 21 ms 23936 KB Output is correct
6 Correct 23 ms 24064 KB Output is correct
7 Correct 26 ms 24704 KB Output is correct
8 Correct 22 ms 23988 KB Output is correct
9 Correct 105 ms 29452 KB Output is correct
10 Correct 21 ms 24064 KB Output is correct
11 Correct 19 ms 24064 KB Output is correct
12 Correct 99 ms 29604 KB Output is correct
13 Correct 129 ms 32572 KB Output is correct
14 Correct 127 ms 30840 KB Output is correct
15 Correct 126 ms 31176 KB Output is correct
16 Correct 119 ms 32544 KB Output is correct
17 Correct 148 ms 30832 KB Output is correct
18 Correct 137 ms 31316 KB Output is correct
19 Execution timed out 791 ms 67416 KB Time limit exceeded
20 Halted 0 ms 0 KB -