Submission #45210151

Source Code Expand

#include <cstdio>
#include <cstdlib>
#include <vector>
#define maxn 200005
using namespace std;

inline void setmin(int& x, int y)
{
	if(y < x) x = y;
}

vector<int> G[maxn], T[maxn << 1];

inline void add_edge(vector<int>* G, int x, int y)
{
	G[x].push_back(y);
	G[y].push_back(x);
}

int dfc, dfn[maxn], low[maxn], top, st[maxn], cnt;

void tarjan(int v)
{
	low[v] = dfn[v] = ++dfc;
	st[++top] = v;
	for(int u: G[v])
		if(!dfn[u])
		{
			tarjan(u);
			setmin(low[v], low[u]);
			if(low[u] == dfn[v])
			{
				add_edge(T, v, ++cnt);
				do add_edge(T, st[top], cnt);
				while(st[top--] != u);
			}
		}
		else setmin(low[v], dfn[u]);
}

int n, m, a, b, c, ct[maxn << 1];
void dfs(int v, int par)
{
	if(v > n)
		for(int u: T[v])
			ct[u] ++;
	if(v == c)
	{
		puts(ct[b]? "Yes": "No");
		exit(0);
	}
	for(int u: T[v])
		if(u != par)
			dfs(u, v);
	if(v > n)
		for(int u: T[v])
			ct[u] --;
}

int main()
{
	scanf("%d%d%d%d%d", &n, &m, &a, &b, &c);
	while(m--)
	{
		int x, y;
		scanf("%d%d", &x, &y);
		add_edge(G, x, y);
	}
	cnt = n;
	tarjan(1);
	dfs(a, -1);
	return 0;
}

Submission Info

Submission Time
Task G - Typical Path Problem
User good_coder_666
Language C++ 20 (gcc 12.2)
Score 575
Code Size 1142 Byte
Status AC
Exec Time 162 ms
Memory 57824 KiB

Compile Error

Main.cpp: In function ‘int main()’:
Main.cpp:62:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   62 |         scanf("%d%d%d%d%d", &n, &m, &a, &b, &c);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:66:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   66 |                 scanf("%d%d", &x, &y);
      |                 ~~~~~^~~~~~~~~~~~~~~~

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 575 / 575
Status
AC × 3
AC × 93
Set Name Test Cases
Sample example_00.txt, example_01.txt, example_02.txt
All example_00.txt, example_01.txt, example_02.txt, hand2_00.txt, hand2_01.txt, hand2_02.txt, hand2_03.txt, hand2_04.txt, hand2_05.txt, hand2_06.txt, hand2_07.txt, hand2_08.txt, hand2_09.txt, hand2_10.txt, hand2_11.txt, hand2_12.txt, hand2_13.txt, hand2_14.txt, hand2_15.txt, hand2_16.txt, hand2_17.txt, hand2_18.txt, hand2_19.txt, hand_00.txt, hand_01.txt, hand_02.txt, hand_03.txt, hand_04.txt, hand_05.txt, hand_06.txt, hand_07.txt, hand_08.txt, hand_09.txt, random2_00.txt, random2_01.txt, random2_02.txt, random2_03.txt, random2_04.txt, random2_05.txt, random2_06.txt, random2_07.txt, random2_08.txt, random2_09.txt, random2_10.txt, random2_11.txt, random2_12.txt, random2_13.txt, random2_14.txt, random2_15.txt, random2_16.txt, random2_17.txt, random2_18.txt, random2_19.txt, random2_20.txt, random2_21.txt, random2_22.txt, random2_23.txt, random2_24.txt, random3_00.txt, random3_01.txt, random3_02.txt, random3_03.txt, random3_04.txt, random3_05.txt, random3_06.txt, random3_07.txt, random3_08.txt, random3_09.txt, random3_10.txt, random3_11.txt, random3_12.txt, random3_13.txt, random3_14.txt, random3_15.txt, random3_16.txt, random3_17.txt, random3_18.txt, random3_19.txt, random_00.txt, random_01.txt, random_02.txt, random_03.txt, random_04.txt, random_05.txt, random_06.txt, random_07.txt, random_08.txt, random_09.txt, random_10.txt, random_11.txt, random_12.txt, random_13.txt, random_14.txt
Case Name Status Exec Time Memory
example_00.txt AC 3 ms 3168 KiB
example_01.txt AC 3 ms 3120 KiB
example_02.txt AC 3 ms 3000 KiB
hand2_00.txt AC 70 ms 23148 KiB
hand2_01.txt AC 73 ms 24092 KiB
hand2_02.txt AC 69 ms 21708 KiB
hand2_03.txt AC 76 ms 26000 KiB
hand2_04.txt AC 70 ms 24204 KiB
hand2_05.txt AC 66 ms 21960 KiB
hand2_06.txt AC 65 ms 22008 KiB
hand2_07.txt AC 74 ms 25884 KiB
hand2_08.txt AC 70 ms 22504 KiB
hand2_09.txt AC 71 ms 23376 KiB
hand2_10.txt AC 54 ms 16576 KiB
hand2_11.txt AC 96 ms 29800 KiB
hand2_12.txt AC 14 ms 4620 KiB
hand2_13.txt AC 17 ms 4436 KiB
hand2_14.txt AC 21 ms 6076 KiB
hand2_15.txt AC 19 ms 5024 KiB
hand2_16.txt AC 48 ms 13992 KiB
hand2_17.txt AC 56 ms 13420 KiB
hand2_18.txt AC 117 ms 36460 KiB
hand2_19.txt AC 77 ms 24748 KiB
hand_00.txt AC 3 ms 3004 KiB
hand_01.txt AC 142 ms 51376 KiB
hand_02.txt AC 108 ms 44184 KiB
hand_03.txt AC 24 ms 5784 KiB
hand_04.txt AC 25 ms 6028 KiB
hand_05.txt AC 149 ms 57544 KiB
hand_06.txt AC 149 ms 57824 KiB
hand_07.txt AC 120 ms 44228 KiB
hand_08.txt AC 139 ms 48532 KiB
hand_09.txt AC 162 ms 57480 KiB
random2_00.txt AC 7 ms 3732 KiB
random2_01.txt AC 16 ms 4620 KiB
random2_02.txt AC 9 ms 4016 KiB
random2_03.txt AC 21 ms 5188 KiB
random2_04.txt AC 16 ms 4284 KiB
random2_05.txt AC 13 ms 4252 KiB
random2_06.txt AC 32 ms 6348 KiB
random2_07.txt AC 19 ms 5204 KiB
random2_08.txt AC 36 ms 6920 KiB
random2_09.txt AC 24 ms 5656 KiB
random2_10.txt AC 24 ms 10152 KiB
random2_11.txt AC 25 ms 7160 KiB
random2_12.txt AC 30 ms 7676 KiB
random2_13.txt AC 29 ms 7264 KiB
random2_14.txt AC 25 ms 6824 KiB
random2_15.txt AC 54 ms 18488 KiB
random2_16.txt AC 46 ms 17164 KiB
random2_17.txt AC 51 ms 14816 KiB
random2_18.txt AC 48 ms 17252 KiB
random2_19.txt AC 44 ms 16856 KiB
random2_20.txt AC 80 ms 24756 KiB
random2_21.txt AC 67 ms 21004 KiB
random2_22.txt AC 125 ms 36492 KiB
random2_23.txt AC 100 ms 28864 KiB
random2_24.txt AC 80 ms 24616 KiB
random3_00.txt AC 88 ms 27520 KiB
random3_01.txt AC 76 ms 25384 KiB
random3_02.txt AC 85 ms 29100 KiB
random3_03.txt AC 54 ms 18644 KiB
random3_04.txt AC 76 ms 25532 KiB
random3_05.txt AC 73 ms 25112 KiB
random3_06.txt AC 44 ms 17656 KiB
random3_07.txt AC 83 ms 28080 KiB
random3_08.txt AC 68 ms 23120 KiB
random3_09.txt AC 68 ms 22796 KiB
random3_10.txt AC 69 ms 22776 KiB
random3_11.txt AC 88 ms 27060 KiB
random3_12.txt AC 50 ms 18848 KiB
random3_13.txt AC 78 ms 27592 KiB
random3_14.txt AC 79 ms 26976 KiB
random3_15.txt AC 55 ms 20580 KiB
random3_16.txt AC 54 ms 19884 KiB
random3_17.txt AC 41 ms 15604 KiB
random3_18.txt AC 55 ms 19812 KiB
random3_19.txt AC 74 ms 25188 KiB
random_00.txt AC 4 ms 3348 KiB
random_01.txt AC 4 ms 3452 KiB
random_02.txt AC 4 ms 3280 KiB
random_03.txt AC 4 ms 3296 KiB
random_04.txt AC 4 ms 3364 KiB
random_05.txt AC 4 ms 3524 KiB
random_06.txt AC 4 ms 3392 KiB
random_07.txt AC 4 ms 3344 KiB
random_08.txt AC 4 ms 3288 KiB
random_09.txt AC 4 ms 3220 KiB
random_10.txt AC 4 ms 3468 KiB
random_11.txt AC 4 ms 3448 KiB
random_12.txt AC 4 ms 3544 KiB
random_13.txt AC 4 ms 3344 KiB
random_14.txt AC 4 ms 3440 KiB