oj.uz

Submission #293849

# Submission time Handle Problem Language Result Execution time Memory
293849 2020-09-08T13:03:25 Z 송준혁(#5802) None (balkan16_acrobat) C++17
0 / 100
 13 ms 15744 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;

int N, M;
int U[303030], V[303030], X[303030];
int dfn[303030], num, D[303030];
vector<int> P[303030];
vector<pii> adj[303030];
vector<pii> O1, O2;

void tr(int u){
	dfn[u] = 1;
	for (pii v : adj[u]) if (!dfn[v.fi]) X[v.se] = 1, tr(v.fi);
}

bool dfs(int u){
	dfn[u] = ++num;
	bool a=false;
	for (pii v : adj[u]){
		if ((dfn[v.fi] && dfn[v.fi]<dfn[u]) || !X[v.se]) continue;
		if (!dfn[v.fi]){
			if (dfs(v.fi)){
				if (U[v.se] == u) O1.pb(pii(u, v.fi));
				continue;
			}
		}
		if (U[v.se] == v.fi) O1.pb(pii(v.fi, u));
		if (a) a = false;
		else a = true;
	}
	return a;
}

int main(){
	scanf("%d %d", &N, &M);
	for (int i=1; i<=M; i++){
		scanf("%d %d", &U[i], &V[i]);
		adj[U[i]].pb(pii(V[i], i));
		if (U[i] != V[i]) adj[V[i]].pb(pii(U[i], i));
		P[U[i]].pb(i), D[V[i]]++;
	}
	for (int i=1; i<=N; i++) if (!dfn[i]) tr(i);
	for (int i=1; i<=N; i++){
		int a=0;
		for (int u : P[i]){
			if (X[u]) continue;
			if (!a) a = u;
			else a = 0;
		}
		if (a) X[a] = 1;
	}
	memset(dfn, 0, sizeof dfn);
	for (int i=1; i<=N; i++) if (!dfn[i]) dfs(i);
	for (pii t : O1) D[t.fi]++, D[t.se]--;
	int a=0;
	for (int i=1; i<=N; i++) if (D[i]&1){
		if (a) O2.pb(pii(a, i)), a=0;
		else a = i;
	}
	printf("%d\n", (int)O1.size()+(int)O2.size());
	for (pii t : O1) printf("1 %d %d\n", t.fi, t.se);
	for (pii t : O2) printf("2 %d %d\n", t.fi, t.se);
	return 0;
}

Compilation message

main.cpp: In function 'int main()':
main.cpp:40:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   40 |  scanf("%d %d", &N, &M);
      |  ~~~~~^~~~~~~~~~~~~~~~~
main.cpp:42:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   42 |   scanf("%d %d", &U[i], &V[i]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 15744 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 35.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 15744 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 35.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 15744 KB Output isn't correct
2 Halted 0 ms 0 KB -