結果

問題 No.3390 Public or Private
コンテスト
ユーザー GaLLium
提出日時 2025-11-21 10:38:28
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 155 ms / 2,000 ms
コード長 2,113 bytes
コンパイル時間 12,558 ms
コンパイル使用メモリ 400,036 KB
実行使用メモリ 150,144 KB
最終ジャッジ日時 2025-11-28 20:58:42
合計ジャッジ時間 16,868 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 27
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#![allow(unused)]
#![allow(non_snake_case)]
#![allow(dead_code)]

fn main() {
   let input_str = std::io::read_to_string(std::io::stdin()).unwrap();
   let mut input = input_str.split_whitespace();
   let mut read_int = ||->usize {input.next().unwrap().parse().unwrap_or(0)};
   
   
   let (N,M) = (read_int(),read_int());
   //クエリに出現するユーザー(高々6000人)のみを見ればいい
   //先読み
   let mut edges=vec![];
   for _ in 0..M{
       edges.push((read_int(),read_int()));
   }
   let Q = read_int();
   let mut querys = vec![];
   let mut appear = vec![];
   for _ in 0..Q{
       let q = read_int();
       if q == 1{
           let (a,b)= (read_int(),read_int());
           querys.push((1,a,b));
           appear.push(a);
           appear.push(b);
       } else{
           let a = read_int();
           read_int();
           querys.push((2,a,0));
           appear.push(a);
       }
   }
   
   //圧縮
   appear.sort();appear.dedup();
   let len = appear.len();
   let mut map = std::collections::HashMap::new();
   for i in 0..len{
       map.insert(appear[i],i);
   }
   
   //もう一度読む
   let mut mat = vec![vec![0;len];len]; //隣接行列
   for &(u,v) in edges.iter(){
       if let Some(&i) = map.get(&u){
           if let Some(&j) = map.get(&v){
               mat[i][j] = 1;
           }
       }
   }
   let mut is_public = vec![true;len];
   let mut public = N; 
   for &(q,a,b) in querys.iter(){
       let i = *map.get(&a).unwrap();
       if q == 1{
           let j = *map.get(&b).unwrap();
           mat[i][j] ^= 1;
       } else{
           is_public[i] ^= true;
           if is_public[i]{
               public += 1;
           } else {
               public -= 1;
           }
       }
        //フォローしている非公開の個数
       let mut cnt = 0;
       for j in 0..len{
           if mat[i][j] == 1 && !is_public[j]{
               cnt += 1;
           }
       }
       let mut ans = public+cnt;
       if is_public[i]{
           ans -= 1;  //自分が公開なら1引く
       }
       println!("{}",ans);
   }
   
}
0