結果

問題 No.3390 Public or Private
コンテスト
ユーザー yu23578
提出日時 2025-11-15 11:43:17
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 757 ms / 2,000 ms
コード長 2,395 bytes
コンパイル時間 2,448 ms
コンパイル使用メモリ 222,916 KB
実行使用メモリ 60,028 KB
最終ジャッジ日時 2025-11-28 20:53:29
合計ジャッジ時間 20,170 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 27
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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

vector<int> zaatu(vector<int> P){//座標圧縮
    int N = P.size();
    vector<int> P_copy = P;
    sort(P_copy.begin(),P_copy.end());
    P_copy.erase(unique(P_copy.begin(),P_copy.end()),P_copy.end());
    vector<int> res;
    for(int i = 0; i < N; i++) res.push_back(lower_bound(P_copy.begin(),P_copy.end(),P[i]) - P_copy.begin());
    return res;
}

signed main(){
  //ステップ1. 入力の受け取り
  vector<int> P; //クエリに関係あるユーザー
  int N,M,Q; cin>>N>>M;
  vector<int> U(M);
  vector<int> V(M);
  for(int i = 0; i < M; i++){
      cin>>U[i]>>V[i];
      P.push_back(U[i]);
      P.push_back(V[i]);
  }
  cin>>Q;
  vector<tuple<int,int,int>> query(Q);
  for(int i = 0; i < Q; i++){
      int a,b,c; cin>>a>>b>>c;
      query[i] = {a,b,c};
      P.push_back(b);
      if(c != -1) P.push_back(c);
  }
  
  //ステップ2. 入力の加工
  vector<int> G = zaatu(P);
  unordered_map<int,int> mp; //ユーザー番号対応表
  for(int i = 0; i < P.size(); i++){
      mp[P[i]] = G[i];
  }
  //ユーザー対応表に従って変更開始
  for(int i = 0; i < M; i++){
      U[i] = mp[U[i]];
      V[i] = mp[V[i]];
  }
  for(int i = 0; i < Q; i++){
      int a = get<0>(query[i]);
      int b = get<1>(query[i]);
      int c = get<2>(query[i]);
      query[i] = {a,mp[b],mp[c]};
  }
  
  //ステップ3. クエリ解答への準備
  vector<set<int>> S(P.size()+2); //「自分のことをフォローしている人」の集合
  for(int i = 0; i < M; i++) S[V[i]].insert(U[i]);
  vector<bool> Status(P.size()+2,true); //trueなら公開、falseなら非公開
  set<int> Private; //ステータスが非公開のユーザーの集合
  
  //ステップ4. クエリへの解答
  for(int i = 0; i < Q; i++){
  	//入力の受け取り
  	int q = get<0>(query[i]);
  	int a = get<1>(query[i]);
  	int b = get<2>(query[i]);
  	
  	//操作
  	if(q == 1){
  		if(S[b].count(a)) S[b].erase(a);
  		else S[b].insert(a);
  	}
  	if(q == 2){
  		if(Status[a]){
  			Status[a] = false;
  			Private.insert(a);
  		}
  		else{
  			Status[a] = true;
  			Private.erase(a);
  		}
  	}
  	
  	//問題への解答
  	int Answer = 0;
  	for(int p:Private){
  		if(S[p].count(a)) Answer++;
  	}
  	Answer += N - (int)(Private.size());
  	if(!Private.count(a)) Answer--;
  	cout << Answer << "\n";
  }
}
0