QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#110405#4892. 序列AK_Dream0 37ms38420kbC++141.8kb2023-06-01 21:24:502023-06-01 21:24:54

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-06-01 21:24:54]
  • 评测
  • 测评结果:0
  • 用时:37ms
  • 内存:38420kb
  • [2023-06-01 21:24:50]
  • 提交

answer

#include <bits/stdc++.h>
#define N 300005
#define pb push_back
using namespace std;

int n, m, c[N], ans[N];
int a[N][3], val[N];
vector<int> V[N], id[2][N], E[N];
int dfn[N], low[N], col[N], stk[N], in[N], tme, top, scc;

inline void adeg(int u, int v) { E[u].pb(v); }
void tarjan(int x) {
	dfn[x] = low[x] = ++tme;
	stk[++top] = x; in[x] = 1;
	for (auto y : E[x]) {
		if (!dfn[y]) tarjan(y), low[x] = min(low[x], low[y]);
		else if (in[y]) low[x] = min(low[x], dfn[y]);
	}	
	if (dfn[x] == low[x]) {
		++scc; int z = 0;
		do {
			z = stk[top--];
			col[z] = scc; in[z] = 0;
		} while (z != x);
	}
}

int main() {
	scanf("%d %d", &n, &m);
	for (int i = 1; i <= m; i++) {
		for (int j = 0; j <= 2; j++) scanf("%d", &a[i][j]);
		scanf("%d", &val[i]);
		for (int j = 0; j <= 2; j++) V[a[i][j]].push_back(val[i]); 
	} 
	int cnt = 0;
	for (int i = 1; i <= n; i++) {
		sort(V[i].begin(),V[i].end()); 
		c[i] = V[i].size();
		for (int j = 0; j < c[i]; j++) {
			id[0][i].pb(++cnt); id[1][i].pb(++cnt);
			if (j) adeg(id[0][i][j-1],id[0][i][j]), adeg(id[1][i][j],id[1][i][j-1]);
		}
	}
	for (int i = 1; i <= m; i++) {
		for (int p:{0,1,2}) for (int q:{0,1,2}) if (p != q) {
			int u = a[i][p], v = a[i][q];
			int up = lower_bound(V[u].begin(),V[u].end(),val[i])-V[u].begin();
			int vp = lower_bound(V[v].begin(),V[v].end(),val[i])-V[v].begin();
			adeg(id[0][u][up], id[1][v][vp]);
			if (up+1<c[u] && vp+1<c[v]) adeg(id[1][u][up+1],id[0][v][vp+1]);
		}
	} 
	for (int i = 1; i <= cnt; i++) if (!dfn[i]) tarjan(i);
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j < c[i]; j++) {
			int u = id[0][i][j], v = id[1][i][j];
			if (col[u] == col[v]) { puts("NO"); return 0; }
			if (col[v] < col[u]) ans[i] = V[i][j];
		} 
	}
	puts("YES");
	for (int i = 1; i <= n; i++) printf("%d ", ans[i]);
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 10ms
memory: 31708kb

input:

10 10
6 3 10 133562624
8 7 6 685486592
4 2 7 332482851
10 8 9 211550017
2 10 1 165556251
10 8 5 211550017
6 8 2 332482851
4 9 2 332482851
8 1 4 193658790
9 6 10 728674154

output:

YES
165556251 332482851 0 193658790 211550017 728674154 685486592 211550017 728674154 133562624 

result:

wrong answer Integer 0 violates the range [1, 10^9]

Subtask #2:

score: 0
Dangerous Syscalls

Test #9:

score: 10
Accepted
time: 37ms
memory: 38420kb

input:

40 9880
4 19 31 610502845
10 19 33 190412843
21 24 39 649028784
16 22 40 569593239
5 9 37 550862419
11 23 40 654613112
6 18 23 492267246
22 23 30 538715841
6 16 24 407919735
5 16 18 388907784
2 16 18 388907784
21 24 28 281403057
7 12 27 451830401
3 11 16 508407438
15 33 36 561955959
6 23 29 70605893...

output:

YES
877488996 197498120 508407438 610502845 209356929 706058934 655952999 624132238 550862419 32695410 654613112 72694954 399757770 396827347 561955959 407919735 779328631 388907784 190412843 657895429 832003778 569593239 492267246 32695410 718125822 812463588 451830401 281403057 877488996 538715841...

result:

ok solution is correct

Test #10:

score: -10
Dangerous Syscalls

input:

80 82160
8 15 41 111467584
35 54 58 471689837
51 66 69 545620573
20 63 76 46182451
15 34 40 54922534
19 27 49 410013534
6 13 18 849916477
3 12 30 436881726
8 23 54 239683045
6 37 40 544597112
29 52 70 792746131
7 52 75 478735558
11 50 74 735803963
4 28 50 415323204
23 54 68 347125331
33 67 70 525526...

output:


result:


Subtask #3:

score: 0
Skipped

Dependency #1:

0%

Subtask #4:

score: 0
Skipped

Dependency #2:

0%