結果
| 問題 | No.1553 Lovely City |
| ユーザー |
 Moss_Local
|
| 提出日時 | 2021-06-18 21:36:09 |
| 言語 | Rust (1.77.0 + proconio) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 6,744 bytes |
| コンパイル時間 | 12,311 ms |
| コンパイル使用メモリ | 387,068 KB |
| 実行使用メモリ | 21,416 KB |
| 最終ジャッジ日時 | 2024-06-22 19:59:50 |
| 合計ジャッジ時間 | 19,220 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge4 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 1 ms
6,816 KB |
| testcase_01 | WA | - |
| testcase_02 | AC | 9 ms
11,436 KB |
| testcase_03 | RE | - |
| testcase_04 | RE | - |
| testcase_05 | WA | - |
| testcase_06 | RE | - |
| testcase_07 | RE | - |
| testcase_08 | RE | - |
| testcase_09 | RE | - |
| testcase_10 | WA | - |
| testcase_11 | RE | - |
| testcase_12 | RE | - |
| testcase_13 | RE | - |
| testcase_14 | RE | - |
| testcase_15 | RE | - |
| testcase_16 | RE | - |
| testcase_17 | WA | - |
| testcase_18 | RE | - |
| testcase_19 | RE | - |
| testcase_20 | RE | - |
| testcase_21 | RE | - |
| testcase_22 | RE | - |
| testcase_23 | RE | - |
| testcase_24 | RE | - |
| testcase_25 | RE | - |
| testcase_26 | RE | - |
| testcase_27 | RE | - |
コンパイルメッセージ
warning: unnecessary parentheses around type
--> src/main.rs:67:15
|
67 | fn readi() -> (i64) {
| ^ ^
|
= note: `#[warn(unused_parens)]` on by default
help: remove these parentheses
|
67 - fn readi() -> (i64) {
67 + fn readi() -> i64 {
|
warning: variable does not need to be mutable
--> src/main.rs:200:9
|
200 | let mut n = graph.len();
| ----^
| |
| help: remove this `mut`
|
= note: `#[warn(unused_mut)]` on by default
warning: variable does not need to be mutable
--> src/main.rs:206:13
|
206 | let mut v = i;
| ----^
| |
| help: remove this `mut`
warning: variable does not need to be mutable
--> src/main.rs:208:17
|
208 | let mut nv = graph[v][j].0;
| ----^^
| |
| help: remove this `mut`
warning: unused variable: `flg`
--> src/main.rs:221:13
|
221 | let mut flg = true;
| ^^^ help: if this is intentional, prefix it with an underscore: `_flg`
|
= note: `#[warn(unused_variables)]` on by default
warning: variable does not need to be mutable
--> src/main.rs:217:9
|
217 | let mut n = graph.len();
| ----^
| |
| help: remove this `mut`
warning: variable does not need to be mutable
--> src/main.rs:221:9
|
221 | let mut flg = true;
| ----^^^
| |
| help: remove this `mut`
warning: variable does not need to be mutable
--> src/main.rs:227:9
|
227 | let mut flg_cycle = true;
| ----^^^^^^^^^
| |
| help: remove this `mut`
warning: unused variable: `i`
--> src/main.rs:239:9
|
239 | for i in 0..m {
| ^ help: if this is intentional, prefix it with an underscore: `_i`
ソースコード
// -*- coding:utf-8-unix -*-
// #![feature(map_first_last)]
#![allow(dead_code)]
#![allow(unused_imports)]
#![allow(unused_macros)]
use std::collections::*;
use std::convert::*;
use std::convert::{From, Into};
use std::fmt::Debug;
use std::fs::File;
use std::io::prelude::*;
use std::io::*;
use std::marker::Copy;
use std::mem::*;
use std::ops::Bound::*;
use std::ops::{Add, Mul, Neg, Sub};
use std::str;
use std::thread::park_timeout;
use std::vec;
use std::{cmp, process::Output};
use std::{cmp::Ordering, env::consts::DLL_PREFIX};
use std::{cmp::Ordering::*, f32::consts::PI};
const INF: i64 = 1223372036854775807;
const UINF: usize = INF as usize;
const FINF: f64 = 122337203685.0;
const INF128: i128 = 1223372036854775807000000000000;
const LINF: i64 = 2147483647;
const MOD: i64 = 1000000007;
// const MOD: i64 = 998244353;
// const MOD: i64 = INF;
const UMOD: usize = MOD as usize;
use std::cmp::*;
use std::collections::*;
use std::io::stdin;
use std::io::stdout;
use std::io::Write;
macro_rules! p {
($x:expr) => {
println!("{}", $x);
};
}
macro_rules! d {
($x:expr) => {
println!("{:?}", $x);
};
}
macro_rules! dd {
(x:expr) => {
dbg!(x);
};
}
// use str::Chars;
// use str::Chars;
#[allow(dead_code)]
fn read<T: std::str::FromStr>() -> T {
let mut s = String::new();
std::io::stdin().read_line(&mut s).ok();
s.trim().parse().ok().unwrap()
}
#[allow(dead_code)]
fn readi() -> (i64) {
let mut str = String::new();
let _ = stdin().read_line(&mut str).unwrap();
let mut iter = str.split_whitespace();
iter.next().unwrap().parse::<i64>().unwrap()
}
#[allow(dead_code)]
fn read_vec<T: std::str::FromStr>() -> Vec<T> {
read::<String>()
.split_whitespace()
.map(|e| e.parse().ok().unwrap())
.collect()
}
#[allow(dead_code)]
fn read_vec2<T: std::str::FromStr>(n: u32) -> Vec<Vec<T>> {
(0..n).map(|_| read_vec()).collect()
}
#[allow(dead_code)]
fn readii() -> (i64, i64) {
let mut str = String::new();
let _ = stdin().read_line(&mut str).unwrap();
let mut iter = str.split_whitespace();
(
iter.next().unwrap().parse::<i64>().unwrap(),
iter.next().unwrap().parse::<i64>().unwrap(),
)
}
fn readff() -> (f64, f64) {
let mut str = String::new();
let _ = stdin().read_line(&mut str).unwrap();
let mut iter = str.split_whitespace();
(
iter.next().unwrap().parse::<f64>().unwrap(),
iter.next().unwrap().parse::<f64>().unwrap(),
)
}
#[allow(dead_code)]
fn readiii() -> (i64, i64, i64) {
let mut str = String::new();
let _ = stdin().read_line(&mut str).unwrap();
let mut iter = str.split_whitespace();
(
iter.next().unwrap().parse::<i64>().unwrap(),
iter.next().unwrap().parse::<i64>().unwrap(),
iter.next().unwrap().parse::<i64>().unwrap(),
)
}
#[allow(dead_code)]
fn readuu() -> (usize, usize) {
let mut str = String::new();
let _ = stdin().read_line(&mut str).unwrap();
let mut iter = str.split_whitespace();
(
iter.next().unwrap().parse::<usize>().unwrap(),
iter.next().unwrap().parse::<usize>().unwrap(),
)
}
fn readcc() -> (char, char) {
let mut str = String::new();
let _ = stdin().read_line(&mut str).unwrap();
let mut iter = str.split_whitespace();
(
iter.next().unwrap().parse::<char>().unwrap(),
iter.next().unwrap().parse::<char>().unwrap(),
)
}
#[allow(dead_code)]
fn readuuu() -> (usize, usize, usize) {
let mut str = String::new();
let _ = stdin().read_line(&mut str).unwrap();
let mut iter = str.split_whitespace();
(
iter.next().unwrap().parse::<usize>().unwrap(),
iter.next().unwrap().parse::<usize>().unwrap(),
iter.next().unwrap().parse::<usize>().unwrap(),
)
}
#[allow(dead_code)]
fn readuuuu() -> (usize, usize, usize, usize) {
let mut str = String::new();
let _ = stdin().read_line(&mut str).unwrap();
let mut iter = str.split_whitespace();
(
iter.next().unwrap().parse::<usize>().unwrap(),
iter.next().unwrap().parse::<usize>().unwrap(),
iter.next().unwrap().parse::<usize>().unwrap(),
iter.next().unwrap().parse::<usize>().unwrap(),
)
}
fn readiiii() -> (i64, i64, i64, i64) {
let mut str = String::new();
let _ = stdin().read_line(&mut str).unwrap();
let mut iter = str.split_whitespace();
(
iter.next().unwrap().parse::<i64>().unwrap(),
iter.next().unwrap().parse::<i64>().unwrap(),
iter.next().unwrap().parse::<i64>().unwrap(),
iter.next().unwrap().parse::<i64>().unwrap(),
)
}
fn topo_sort_dfs(
v: usize,
graph: &Vec<Vec<(usize, usize)>>,
used: &mut Vec<usize>,
data: &mut Vec<usize>,
) {
if used[v] == 1 {
return;
}
used[v] = 1;
for i in graph[v].iter() {
let nv = (*i).0;
if used[nv] == 1 {
continue;
}
topo_sort_dfs(nv, &graph, used, data);
}
data.push(v);
return;
}
fn topo_cycle_ditect(graph: &Vec<Vec<(usize, usize)>>, sorted: &Vec<usize>) -> bool {
let mut flg = false;
// let mut = 0 as usize;
let mut n = graph.len();
let mut num = vec![0; n];
for i in 0..n {
num[sorted[i]] = i;
}
for i in 0..n {
let mut v = i;
for j in 0..graph[v].len() {
let mut nv = graph[v][j].0;
if num[v] > num[nv] {
flg = true;
}
}
}
return flg;
}
fn topo_sort(graph: &Vec<Vec<(usize, usize)>>) -> Vec<usize> {
let mut n = graph.len();
// let mut = 0 as usize;c
let mut used = vec![0; n];
let mut res = vec![0; 0];
let mut flg = true;
for i in 0..n {
topo_sort_dfs(i, &graph, &mut used, &mut res);
}
res.reverse();
let mut flg_cycle = true;
if flg_cycle {
if topo_cycle_ditect(&graph, &res) {
return vec![0; 0];
}
}
return res;
}
fn solve() {
let (n, m) = readuu();
let mut graph = vec![vec![(0 as usize, 0 as usize); (0) as usize]; (n) as usize];
for i in 0..m {
let (mut a, mut b) = readuu();
a -= 1;
b -= 1;
graph[a].push((b, 1));
}
let ts = topo_sort(&graph);
let mut visited = vec![0; n];
let mut res = vec![];
for i in 0..n {
let v = ts[i];
for j in 0..graph[v].len() {
let nv = graph[v][j].0;
if visited[nv] == 0 {
visited[nv] = 1;
res.push((v + 1, nv + 1));
}
}
}
p!(res.len());
for i in 0..res.len() {
println!("{} {}", res[i].0, res[i].1);
}
return;
}
fn main() {
solve();
}