QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#353114#1301. 括号路径penguin13348 389ms200768kbC++232.6kb2024-03-13 21:22:592024-03-13 21:22:59

Judging History

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

  • [2024-03-13 21:22:59]
  • 评测
  • 测评结果:48
  • 用时:389ms
  • 内存:200768kb
  • [2024-03-13 21:22:59]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define pi pair<int, int>
#define pii pair<int, pi>
#define fi first
#define se second
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

int n, m, k;
map <pair <int, stack <int> >, int> mp;
vector <pi> adj[300005];
int endp, reach = 0;

void dfs(int x, stack <int> s){
	if(s.size() > n)return;
	if(mp.find({x, s}) != mp.end())return;
	if(x == endp){
		if(s.empty())reach = 1;
		//return;
	}
	mp[{x, s}] = 1;
	for(auto [i, j] : adj[x]){
		stack <int> ss = s;
		if(!ss.empty() && ss.top() == -j)ss.pop();
		else {
			if(j < 0)continue;
			ss.push(j);
		}
		dfs(i, ss);
		if(reach)return;
	}
	
}
bool vis[3005][3005];
int marked[3005];
vector <int> shit;
void go(int x, int val){
	if(val > n)return;
	if(vis[x][val])return;
	vis[x][val] = 1;
	if(!val){
		marked[x] = 1;
		//cout << x << ' ';
		shit.push_back(x);
	}
	for(auto [i, j] : adj[x]){
		if(val + j < 0)continue;
		go(i, val + j);
	}
}

const int mod = 1e9 + 7;
int dist[3005], dist2[3005];
vector <pi> fw[300005], back[300005];

void solve(){
	cin >> n >> m >> k;
	for(int i = 1; i <= m; i++){
		int a, b, c; cin >> a >> b >> c;
		adj[a].push_back({b, c});
		adj[b].push_back({a, -c});
		fw[a].push_back({b, c});
		back[b].push_back({a, c});
	}
	if(k == 1){
		int ans = 0;
		for(int i = 1; i <= n; i++){
			if(marked[i])continue;
			shit.clear();
			go(i, 0);
			ans += shit.size() * (shit.size() - 1) / 2;
		}
		cout << ans;
		return;
	}
	else if(m <= n - 1){
		int ans = 0;
		for(int i = 1; i <= n; i++){
			for(int j = 1; j <= n; j++)dist[j] = 1e9;
			for(int j = 1; j <= n; j++)dist2[j] = -1e9;
			dist[i] = dist2[i] = 0;
			queue <int> q;
			q.push(i);
			while(!q.empty()){
				int x = q.front(); q.pop();
				for(auto [a, b] : back[x]){
					dist[a] = (dist[x] * (k + 1) + b) % mod;
					q.push(a);
				}
			}
			map <int, int> mp;
			for(int j = 1; j <= n; j++){
				if(dist[j] != 1e9){
					ans += mp[dist[j]]++;
				}
			}
		}
		cout << ans << '\n';
		return;
	}
	int ans = 0;
	for(int i = 1; i <= n; i++){
		for(int j = i + 1; j <= n; j++){
			endp = j;
			reach = 0;
			mp.clear();
			stack <int> tmp;
			dfs(i, tmp);
			if(reach){
				//cout << i << ' ' << j << '\n';
				ans++;
			}
		}
	}
	cout << ans;
}

main(){
	ios::sync_with_stdio(0);cin.tie(0);
	int tc = 1;
	//cin >> tc;
	for(int tc1=1;tc1<=tc;tc1++){
		// cout << "Case #" << tc1 << ": ";
		solve();
	}
}

详细

Test #1:

score: 4
Accepted
time: 2ms
memory: 3676kb

input:

4 5 2
3 1 2
4 1 2
2 3 1
4 2 1
1 3 1

output:

2

result:

ok 1 number(s): "2"

Test #2:

score: 4
Accepted
time: 1ms
memory: 3724kb

input:

4 5 2
3 4 2
2 4 2
2 4 1
2 1 1
2 3 2

output:

1

result:

ok 1 number(s): "1"

Test #3:

score: 4
Accepted
time: 1ms
memory: 3920kb

input:

4 5 2
1 3 1
1 4 2
1 2 1
2 3 1
2 1 1

output:

1

result:

ok 1 number(s): "1"

Test #4:

score: 4
Accepted
time: 0ms
memory: 3868kb

input:

4 5 2
2 4 1
3 4 1
1 2 2
4 2 2
3 1 1

output:

2

result:

ok 1 number(s): "2"

Test #5:

score: 4
Accepted
time: 13ms
memory: 4880kb

input:

8 10 2
4 8 2
5 2 2
8 7 1
4 1 1
5 7 2
5 7 2
7 8 1
2 7 2
6 5 1
8 7 2

output:

7

result:

ok 1 number(s): "7"

Test #6:

score: 4
Accepted
time: 16ms
memory: 4888kb

input:

8 10 2
2 6 1
7 8 2
3 6 2
3 7 1
8 7 1
8 7 1
7 2 1
1 5 2
2 8 2
7 8 1

output:

6

result:

ok 1 number(s): "6"

Test #7:

score: 4
Accepted
time: 37ms
memory: 5600kb

input:

8 10 2
6 7 2
2 6 1
2 7 2
1 3 1
6 2 2
2 8 2
8 6 2
1 2 2
6 8 1
5 7 2

output:

10

result:

ok 1 number(s): "10"

Test #8:

score: 4
Accepted
time: 18ms
memory: 4676kb

input:

8 10 2
3 8 2
3 7 1
6 8 1
6 1 2
3 4 1
8 5 1
4 7 1
7 2 2
1 6 1
6 3 1

output:

6

result:

ok 1 number(s): "6"

Test #9:

score: 4
Accepted
time: 362ms
memory: 200768kb

input:

3000 6000 1
1239 1740 1
2927 433 1
1102 329 1
2296 2920 1
2869 2230 1
266 466 1
2971 426 1
1268 2361 1
1777 749 1
648 2273 1
308 2354 1
759 2714 1
594 2679 1
1351 1623 1
1289 68 1
167 193 1
1014 1181 1
1297 2045 1
2496 807 1
2604 1723 1
1516 213 1
1953 1190 1
259 620 1
1425 775 1
1613 2083 1
1025 13...

output:

3306307

result:

ok 1 number(s): "3306307"

Test #10:

score: 4
Accepted
time: 389ms
memory: 200696kb

input:

3000 6000 1
2950 2229 1
1031 1727 1
1170 2342 1
707 1346 1
635 1872 1
2884 1512 1
1931 1591 1
191 1928 1
2185 440 1
1628 1931 1
330 306 1
120 2782 1
146 1519 1
2766 112 1
2801 2180 1
2182 610 1
1540 1407 1
2220 1944 1
298 181 1
936 1971 1
560 2197 1
114 1750 1
994 2151 1
1142 1842 1
2533 1918 1
502 ...

output:

3252528

result:

ok 1 number(s): "3252528"

Test #11:

score: 4
Accepted
time: 341ms
memory: 197920kb

input:

3000 6000 1
1435 2449 1
1950 1594 1
526 1195 1
1414 2093 1
433 2735 1
1883 2454 1
1238 2016 1
435 68 1
2155 1716 1
82 2587 1
1523 2603 1
1373 2260 1
1442 1013 1
661 2038 1
1973 1593 1
926 415 1
1754 968 1
2304 152 1
1499 435 1
2637 2270 1
278 2560 1
2136 2896 1
456 2375 1
2569 1575 1
1732 834 1
830 ...

output:

3324331

result:

ok 1 number(s): "3324331"

Test #12:

score: 4
Accepted
time: 360ms
memory: 196020kb

input:

3000 6000 1
1673 1484 1
1006 1316 1
2889 171 1
609 463 1
2265 1207 1
1327 677 1
2874 1405 1
30 2254 1
1606 778 1
275 1762 1
970 2880 1
2099 147 1
59 985 1
982 1438 1
1938 770 1
538 936 1
1574 1465 1
2805 2022 1
69 336 1
789 920 1
35 1232 1
712 560 1
374 1203 1
1799 2721 1
2601 2122 1
428 1276 1
1184...

output:

3311453

result:

ok 1 number(s): "3311453"

Test #13:

score: 0
Wrong Answer
time: 13ms
memory: 6180kb

input:

3000 2999 2
2913 837 2
2913 404 1
1533 837 1
1533 2487 1
2913 882 1
915 882 2
882 2402 2
1533 2657 2
2487 638 2
2657 75 2
638 472 2
638 908 1
996 882 1
1241 2402 2
591 1241 1
2394 2487 1
638 84 1
75 1147 1
170 2657 1
1147 310 1
300 472 2
908 411 1
2913 1011 1
84 1918 2
407 638 2
1533 2216 1
2216 180...

output:

21587

result:

wrong answer 1st numbers differ - expected: '2972', found: '21587'

Test #14:

score: 0
Wrong Answer
time: 13ms
memory: 6240kb

input:

3000 2999 2
2913 837 1
404 837 1
1533 837 2
2487 837 2
2913 882 2
1533 915 2
915 2402 2
2657 404 2
882 638 2
837 75 2
472 2913 2
908 2913 1
996 882 1
1241 638 1
638 591 2
882 2394 1
2657 84 1
1147 882 1
837 170 2
591 310 2
472 300 2
908 411 1
1011 1241 1
1918 310 1
407 404 2
915 2216 1
1806 2216 1
2...

output:

13905

result:

wrong answer 1st numbers differ - expected: '2732', found: '13905'

Test #15:

score: 0
Wrong Answer
time: 9ms
memory: 6412kb

input:

3000 2999 2
837 2913 1
2913 404 2
1533 2913 2
2487 2913 1
404 882 1
404 915 1
882 2402 1
2657 2487 1
2402 638 1
2487 75 2
915 472 1
915 908 1
404 996 2
1241 472 2
591 2657 1
882 2394 1
84 2402 1
1147 591 1
915 170 1
882 310 2
591 300 2
411 2657 2
2394 1011 1
411 1918 1
407 2657 1
2216 1011 1
1533 18...

output:

35820

result:

wrong answer 1st numbers differ - expected: '3263', found: '35820'

Test #16:

score: 0
Wrong Answer
time: 9ms
memory: 6432kb

input:

3000 2999 2
837 2913 2
2913 404 1
1533 2913 1
837 2487 1
404 882 1
915 404 2
2402 1533 1
2402 2657 2
2913 638 2
75 2913 1
75 472 2
908 2487 1
996 472 2
1241 404 2
591 75 2
2394 75 1
2402 84 1
1147 75 2
2402 170 2
310 908 2
170 300 2
75 411 2
915 1011 1
1918 75 2
411 407 2
591 2216 1
1011 1806 2
1147...

output:

15125

result:

wrong answer 1st numbers differ - expected: '2844', found: '15125'

Test #17:

score: 0
Time Limit Exceeded

input:

300000 299999 2
226607 242996 1
196602 242996 2
101456 242996 1
45720 226607 1
242996 106478 1
226607 74383 2
232752 101456 1
55049 232752 2
226607 192217 1
35296 74383 1
192217 286621 2
71800 101456 1
71800 287311 2
282373 196602 1
149651 282373 2
245286 106478 2
282373 291356 2
272972 74383 1
1671...

output:


result:


Test #18:

score: 0
Time Limit Exceeded

input:

300000 299999 2
73200 174516 2
153341 73200 2
153341 71485 1
73200 292257 1
153341 185727 1
153341 278048 1
174516 77263 1
185727 213836 1
71485 147158 2
91541 153341 1
73200 205061 1
292257 238251 2
274719 73200 1
116566 91541 1
147158 220606 2
185727 220227 1
127555 238251 2
258405 220227 2
115319...

output:


result:


Test #19:

score: 0
Time Limit Exceeded

input:

300000 299999 2
174516 73200 1
174516 153341 1
174516 71485 2
292257 153341 2
292257 185727 2
71485 278048 1
77263 292257 2
278048 213836 1
147158 73200 1
292257 91541 1
205061 91541 1
238251 213836 1
205061 274719 2
116566 292257 1
73200 220606 1
292257 220227 1
278048 127555 2
238251 258405 1
7320...

output:


result:


Test #20:

score: 0
Time Limit Exceeded

input:

300000 299999 2
72111 268526 2
176640 72111 2
72111 25153 2
176640 183934 2
98063 183934 1
9751 72111 2
176640 258467 2
242290 25153 2
40118 25153 1
136412 176640 2
92133 72111 2
92331 176640 1
283286 40118 1
176640 83421 2
72111 244881 1
5787 258467 2
222867 242290 1
98063 55075 1
297294 55075 2
29...

output:


result:


Test #21:

score: 0
Time Limit Exceeded

input:

300000 600000 50
14868 266444 24
107646 120858 29
145597 144649 18
5798 242942 44
130806 255066 2
137421 131698 42
232007 79600 13
230631 56780 42
116290 195485 15
277206 110652 41
17195 75692 16
63857 86868 22
151546 231440 25
245915 131598 12
95786 4146 12
95632 118765 17
242249 4096 21
129651 491...

output:


result:


Test #22:

score: 0
Time Limit Exceeded

input:

300000 600000 50
248249 58279 41
5370 248476 46
109005 172385 10
281490 111909 13
121762 68485 29
192267 2000 1
89696 254672 1
44850 154565 45
285571 298168 34
190849 164952 40
233661 282335 34
90417 78056 38
35564 89518 44
99390 278646 4
12525 187253 6
248315 265937 5
115414 184345 9
164730 102826 ...

output:


result:


Test #23:

score: 0
Time Limit Exceeded

input:

300000 600000 50
46084 188175 39
273964 223141 31
126412 210480 17
124773 274098 15
71941 58914 21
240324 59030 45
125834 98862 18
296835 1381 18
286670 161485 27
102847 179956 16
116221 245612 23
225330 65587 13
32871 130137 20
262170 15577 30
136029 143696 1
91411 284158 43
53632 149813 33
20307 1...

output:


result:


Test #24:

score: 0
Time Limit Exceeded

input:

300000 600000 50
182738 52409 1
110533 49354 41
230616 98657 42
194919 172023 47
296699 113347 39
170721 295422 44
184728 186406 32
11971 177481 34
148953 146654 37
223873 178617 17
297433 150084 42
111395 141238 14
282185 93711 38
117822 141184 14
250030 279405 28
202347 206233 21
277610 297354 4
3...

output:


result:


Test #25:

score: 0
Time Limit Exceeded

input:

300000 600000 50
158973 244628 16
246492 227212 33
161971 229072 42
53166 119367 3
54422 223149 3
36662 244471 27
238142 292144 10
186871 208089 18
68132 238600 31
185264 208946 20
118206 7586 48
228884 91442 34
173431 234737 10
188679 293253 18
142549 217575 39
147624 17400 39
122387 64740 39
16295...

output:


result: