제출 #314641

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
314641		CaroLinda	다리 (APIO19_bridges)	C++14	73 / 100	3081 ms	24556 KiB

bridges

#include <bits/stdc++.h>

static struct FASTIO {

  char READ_CHARACTER; bool REMAINING_CHARACTER = false;

  inline void ignore(); inline void flush();

  template <typename T> inline bool READ_INT(T &x); template <typename T> inline bool READ_STRING(T &x);
  /*                                                          Fast I/O Code Optimizer                                                          */
  template<size_t N> inline bool READ_CHAR_ARRAY(char (&x)[N]); template<size_t N> inline bool READ_VAR(char (&x)[N]);
  /*                    A tool to optimize execution time of C++ codes by replacing methods of reading and writing variables                   */
  template <typename T> inline bool READ_CHAR(T &x); inline bool READ_CHAR_ARRAY(char*& x); inline bool READ_GETLINE(std::string &x);
  /*                                                    Use it on fastio.pythonanywhere.com                                                    */
  template <typename T> inline bool READ_FLOAT(T &x); template <typename T> inline bool READ_DOUBLE(T &x);
  /*                                          Github Project: github.com/bfs07/Fast-IO-Code-Optimizer                                          */
  template<std::size_t N> inline bool READ_BITSET(std::bitset<N> &bit); template<std::size_t N> inline bool READ_VAR(std::bitset<N> &bit);
  inline bool READ_VAR(bool &x); inline bool READ_VAR(short int &x); inline bool READ_VAR(int &x); 
  inline bool READ_VAR(long int &x); inline bool READ_VAR(long long int &x); inline bool READ_VAR(unsigned short int &x);
  inline bool READ_VAR(unsigned int &x); inline bool READ_VAR(unsigned long &x); inline bool READ_VAR(unsigned long long &x);
  inline bool READ_VAR(std::string &x); inline bool READ_VAR(char &x); inline bool READ_VAR(char*& x); inline bool READ_VAR(float &x);
  inline bool READ_VAR(double &x); inline bool READ_VAR(long double &x); template <typename T> inline void WRITE_INT(T x);
  inline void WRITE_STRING(std::string &x); inline void WRITE_CHAR(char x); inline void WRITE_CHAR_ARRAY(const char *x);
  inline void WRITE_FLOAT(float x); template <typename T> inline void WRITE_DOUBLE(T x); inline void WRITE_VAR(bool x);
  inline void WRITE_VAR(short int x); inline void WRITE_VAR(int x); inline void WRITE_VAR(long int x); inline void WRITE_VAR(long long int x);
  inline void WRITE_VAR(unsigned short int x); inline void WRITE_VAR(unsigned int x); inline void WRITE_VAR(unsigned long x);
  inline void WRITE_VAR(unsigned long long x); inline void WRITE_VAR(char x); inline void WRITE_VAR(const char *x); 
  inline void WRITE_VAR(std::string &x); inline void WRITE_VAR(float x); inline void WRITE_VAR(double x); inline void WRITE_VAR(long double x);
  template<std::size_t N> inline void WRITE_VAR(std::bitset<N> &bit); template<std::size_t N> inline void WRITE_BITSET(std::bitset<N> &bit);

} __FIO__;


#include <bits/stdc++.h>

#define all(x) x.begin(),x.end()
#define ff first
#define ss second
#define ll long long
#define sz(x) (int)(x.size())
#define perfectQ 600
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")

 

const int MAX_COMPRESSION = 2e5+10 ;	
const int MAXQ = 1e5+10 ;
const int MAXM = 1e5+10 ;
const int MAXN = 5e4+10 ;

using namespace std ;

int N , M , Q ;
int indexEdge[MAXM] ;
int U[MAXM] , V[MAXM] , W[MAXM] ;
int ansQueries[MAXQ] ;
vector<int> freq[ MAX_COMPRESSION ] , smallSweep[ MAX_COMPRESSION ] ;
pair<int,int> queries[MAXQ] ;
bool jaPassei[MAXM] ;

 
stack<int> st; 
int pai[MAXN] ;
int componentSize[MAXN] ;

void rollback(int moment)
{
	while(sz(st) > moment)
	{
		int x = st.top() ;
		st.pop() ;

		componentSize[ pai[x] ] -= componentSize[x] ;
		pai[x] = x ;

	}
}

int find(int x)
{
	while(x != pai[x]) x = pai[x] ;
	return x; 
}

void join(int x, int y)
{
	x = find(x) ;
	y = find(y) ;

	if(x == y) return ;

	if( componentSize[x] > componentSize[y] )
		swap(x,y) ;

	componentSize[y] += componentSize[x] ;
	st.push( x ) ;
	pai[x] = y ;

}

void debugTime()
{
	for(int i = 1 ; i <= M ; i++ ) __FIO__.WRITE_VAR(U[i]), __FIO__.WRITE_VAR(" "), __FIO__.WRITE_VAR(V[i]), __FIO__.WRITE_VAR(" "), __FIO__.WRITE_VAR(W[i]), putchar('\n');
	__FIO__.WRITE_VAR("Printing queries"), putchar('\n');
	for(int i = 1 ; i <= Q; i++ )
	{
		if(queries[i].second > 0 )
		{
			__FIO__.WRITE_VAR("1 "), __FIO__.WRITE_VAR(queries[i].second), __FIO__.WRITE_VAR(" "), __FIO__.WRITE_VAR(queries[i].first), putchar('\n');
		}
		else __FIO__.WRITE_VAR("2 "), __FIO__.WRITE_VAR(queries[i].second), __FIO__.WRITE_VAR(" "), __FIO__.WRITE_VAR(queries[i].first), putchar('\n');
	} 
	putchar('\n');
}

int main()
{

	scanf("%d%d", &N , &M ) ;

	vector<int> compression ;

	for(int i = 1 ; i <= M ; i++ )
	{
		scanf("%d%d%d", &U[i], &V[i], &W[i] ) ;
		compression.push_back(W[i]) ;
	}

	scanf("%d", &Q ) ;

	for(int i = 1 , t ; i <= Q ; i++ )
	{
		scanf("%d%d%d", &t, &queries[i].first, &queries[i].second ) ;

		swap(queries[i].first, queries[i].second) ;

		if(t == 1)  
		{
			compression.push_back(queries[i].first) ;
			continue ;
		}
	
		 
		compression.push_back( queries[i].first ) ;
		queries[i].second *= -1 ;

	}

	sort(all(compression)) ;
	compression.erase( unique(all(compression)) , compression.end() ) ;

	for(int i = 1 ; i <= M ; i++ )
		W[i] = lower_bound(all(compression) , W[i] ) - compression.begin() ;

	for(int i = 1 ; i <= Q ; i++ )
	{
		int &x = queries[i].first ;
		int y = queries[i].second ;

		x = lower_bound(all(compression), x) - compression.begin() ;
	}

	 

	for(int i = 1 ; i <= M ; i++ )
	{
		indexEdge[i] = sz( freq[ W[i] ] ) ;
		freq[ W[i] ].push_back(i) ;
	}

	for(int i = 1 ; i <= Q ; i += perfectQ )
	{

		while(!st.empty()) st.pop() ;
		for(int j = 1 ; j <= N ; j++ ) 
		{
			pai[j] = j ;
			componentSize[j] = 1 ;
		}

		vector<int> updates ;

		for(int j = i ; j < min(i+perfectQ,Q+1) ; j++ )
		{
			if( queries[j].second > 0 )
			{
				updates.push_back(j) ;

				int m = queries[j].second ;
				
				if( indexEdge[m] == -1 ) continue ;

				swap( freq[ W[m] ][ indexEdge[m] ] , freq[ W[m] ][ sz(freq[W[m]])-1 ] ) ;
				freq[ W[m] ].pop_back() ;

				indexEdge[ freq[W[m]][indexEdge[m]] ] = indexEdge[m] ;
				indexEdge[m] = -1 ;

			}
			else smallSweep[ queries[j].first ].push_back(j) ;
		}

		 
		for(int j = sz(compression)-1 ; j >= 0 ; j-- )
		{
			for(int g : freq[j] ) join( U[g] , V[g] ) ;

			for(int g : smallSweep[j] ) 
			{
				vector<int> vec ;
				int moment = sz(st) ;

				for(int k = sz(updates)-1 ; k >= 0 ; k-- )
				{
					int a = queries[ updates[k] ].first ;
					int b = queries[ updates[k] ].second ;

					if(updates[k] > g || jaPassei[b]) continue ;

					jaPassei[b] = true ;

					if( a >= j ) join(U[b], V[b] ) ;
				}

				for(int k = sz(updates)-1 ; k >= 0 ; k-- )
				{
					int a = queries[ updates[k] ].first ;
					int b = queries[ updates[k] ].second ;

					if(!jaPassei[b] && W[b] >= j ) 
						join(U[b], V[b] ) ;
				}

				for(int k : updates ) jaPassei[ queries[k].second ]  = false ;

				ansQueries[g] = componentSize[ find( -queries[g].second ) ] ;
				rollback(moment) ;
			}

			smallSweep[j].clear() ;

		}
		
		for(int k = sz(updates)-1 ; k >= 0 ; k-- )
		{
			int a = queries[ updates[k] ].first ;
			int b = queries[ updates[k] ].second ;

			if(indexEdge[b] != -1) continue ;

			W[b] = a ;
			indexEdge[b] = sz(freq[a]) ;
			freq[a].push_back(b) ;

		}
	}

	for(int i = 1 ; i <= Q ; i++ ) 
		if( queries[i].second < 0  ) printf("%d\n" , ansQueries[i]) ;

}

#undef all
#undef sz
#undef all
#undef ff
#undef ss
#undef ll
#undef sz
#undef perfectQ

inline void FASTIO::ignore() {
  if(REMAINING_CHARACTER == true) REMAINING_CHARACTER = false; else READ_CHARACTER = getchar();
}

inline void FASTIO::flush() {
  fflush(stdout);
}

// cin modifications

template <typename T>
inline bool FASTIO::READ_INT(T &x) {
  x = 0; T sig = 1;
  if(!REMAINING_CHARACTER) READ_CHARACTER = getchar(), REMAINING_CHARACTER = true; else REMAINING_CHARACTER = false;
  while (!isdigit(READ_CHARACTER) && READ_CHARACTER != EOF) sig = (READ_CHARACTER == '-' ? -sig : sig), READ_CHARACTER = getchar();
  if(READ_CHARACTER == EOF) return REMAINING_CHARACTER = false, false;
  while (isdigit(READ_CHARACTER)) x = x * 10 + READ_CHARACTER - '0', READ_CHARACTER = getchar();
  x *= sig; REMAINING_CHARACTER = true;
  return true;
}

template <typename T>
inline bool FASTIO::READ_STRING(T &x) {
  x = "";
  if(!REMAINING_CHARACTER) READ_CHARACTER = getchar(), REMAINING_CHARACTER = true; else REMAINING_CHARACTER = false;
  while ((READ_CHARACTER == '\n' || READ_CHARACTER == '\t' || READ_CHARACTER == ' ')) READ_CHARACTER = getchar();
  if(READ_CHARACTER == EOF) return REMAINING_CHARACTER = false, false;
  while ((READ_CHARACTER != '\n' && READ_CHARACTER != '\t' && READ_CHARACTER != ' ' && READ_CHARACTER != EOF)) x += READ_CHARACTER, READ_CHARACTER = getchar();
  REMAINING_CHARACTER = true;
  return true;
}

inline bool FASTIO::READ_GETLINE(std::string &x) {
  x = "";
  if(!REMAINING_CHARACTER) READ_CHARACTER = getchar(), REMAINING_CHARACTER = true; else REMAINING_CHARACTER = false;
  if(READ_CHARACTER == EOF) return REMAINING_CHARACTER = false, false;
  while ((READ_CHARACTER != '\n' && READ_CHARACTER != EOF)) x += READ_CHARACTER, READ_CHARACTER = getchar();
  REMAINING_CHARACTER = false;
  return true;
}

template <typename T>
inline bool FASTIO::READ_CHAR(T &x) {
  if(!REMAINING_CHARACTER) READ_CHARACTER = getchar(), REMAINING_CHARACTER = true; else REMAINING_CHARACTER = false;
  if(READ_CHARACTER == EOF) return REMAINING_CHARACTER = false, false;
  while ((READ_CHARACTER == '\n' || READ_CHARACTER == '\t' || READ_CHARACTER == ' ')) READ_CHARACTER = getchar();
  x = READ_CHARACTER; REMAINING_CHARACTER = false;
  return true;
}


template<size_t N>
inline bool FASTIO::READ_CHAR_ARRAY(char (&x)[N]) {
  if(!REMAINING_CHARACTER) READ_CHARACTER = getchar(), REMAINING_CHARACTER = true; else REMAINING_CHARACTER = false;
  while ((READ_CHARACTER == '\n' || READ_CHARACTER == '\t' || READ_CHARACTER == ' ')) READ_CHARACTER = getchar();
  if(READ_CHARACTER == EOF) return REMAINING_CHARACTER = false, false;
  char *ptr = &x[0];
  while ((READ_CHARACTER != '\n' && READ_CHARACTER != '\t' && READ_CHARACTER != ' ' && READ_CHARACTER != EOF)) *ptr++ = READ_CHARACTER, READ_CHARACTER = getchar();
  *ptr = '\0', REMAINING_CHARACTER = true;
  return true;
}

inline bool FASTIO::READ_CHAR_ARRAY(char*& x) {
  std::string y;
  if(READ_STRING(y) == false)
    return false;
  x = new char[(int)y.size() + 1];
  strcpy(x, y.c_str());
  return true;
}

template <typename T>
inline bool FASTIO::READ_FLOAT(T &x) {
  return (scanf("%f", &x) != EOF);
}

template <typename T>
inline bool FASTIO::READ_DOUBLE(T &x) {
  double y;
  if(scanf("%lf", &y) == EOF) return false;
  x = y;
  return true;
}

template<std::size_t N>
inline bool FASTIO::READ_BITSET(std::bitset<N> &x) {
  if(!REMAINING_CHARACTER) READ_CHARACTER = getchar(), REMAINING_CHARACTER = true; else REMAINING_CHARACTER = false;
  while ((READ_CHARACTER == '\n' || READ_CHARACTER == '\t' || READ_CHARACTER == ' ')) READ_CHARACTER = getchar();
  if(READ_CHARACTER == EOF) return REMAINING_CHARACTER = false, false;
  int i = 0; REMAINING_CHARACTER = true;
  while (READ_CHARACTER == '0' || READ_CHARACTER == '1') x[i++] = READ_CHARACTER - '0', READ_CHARACTER = getchar();
  return true;
}

inline bool FASTIO::READ_VAR(short int &x) {
  return READ_INT(x);    
}

inline bool FASTIO::READ_VAR(int &x) {
  return READ_INT(x);    
}

inline bool FASTIO::READ_VAR(long int &x) {
  return READ_INT(x);    
}

inline bool FASTIO::READ_VAR(long long int &x) {
  return READ_INT(x);    
}

inline bool FASTIO::READ_VAR(unsigned short int &x) {
  return READ_INT(x);    
}

inline bool FASTIO::READ_VAR(unsigned int &x) {
  return READ_INT(x);    
}

inline bool FASTIO::READ_VAR(unsigned long &x) {
  return READ_INT(x);    
}

inline bool FASTIO::READ_VAR(unsigned long long &x) {
  return READ_INT(x);    
}

inline bool FASTIO::READ_VAR(std::string &x) {
  return READ_STRING(x);    
}

inline bool FASTIO::READ_VAR(char &x) {
  return READ_CHAR(x);
}

template<size_t N>
inline bool FASTIO::READ_VAR(char (&x)[N]) {
  return READ_CHAR_ARRAY(x);
}

inline bool FASTIO::READ_VAR(char*& x) {
  return READ_CHAR_ARRAY(x);
}

inline bool FASTIO::READ_VAR(float &x) {
  return READ_FLOAT(x);
}

inline bool FASTIO::READ_VAR(double &x) {
  return READ_DOUBLE(x);
}

inline bool FASTIO::READ_VAR(long double &x) {
  return READ_DOUBLE(x);
}

template<std::size_t N>
inline bool FASTIO::READ_VAR(std::bitset<N> &x) {
  return READ_BITSET(x);
}

// cout modifications

template <typename T>
inline void FASTIO::WRITE_INT(T x) {
  if (x < 0) {putchar('-'); x = -x; }
  char writeBuffer[20], *writePtr = writeBuffer;
  do {
    *writePtr++ = '0' + x % 10;
    x /= 10;
  }
  while (x);
  do  { putchar(*--writePtr); }
  while (writePtr > writeBuffer);
}

inline void FASTIO::WRITE_CHAR(char x) {
  putchar(x);
}

inline void FASTIO::WRITE_CHAR_ARRAY(const char *x) {
  while(*x != '\0')
    putchar(*x++);
}

inline void FASTIO::WRITE_STRING(std::string &x) {
  for(char c: x) 
    putchar(c);
}

inline void FASTIO::WRITE_FLOAT(float x) {
  printf("%f", x);
}

template <typename T>
inline void FASTIO::WRITE_DOUBLE(T x) {
  printf("%lf", (double)x);
}

template<std::size_t N>
inline void FASTIO::WRITE_BITSET(std::bitset<N> &x) {
  for(int i = (int)x.size() - 1; i >= 0; i--)
    putchar(x[i] + 48);
}

inline void FASTIO::WRITE_VAR(bool x) {
  WRITE_INT(x);
}

inline void FASTIO::WRITE_VAR(short int x) {
  WRITE_INT(x);    
}

inline void FASTIO::WRITE_VAR(int x) {
  WRITE_INT(x);    
}

inline void FASTIO::WRITE_VAR(long int x) {
  WRITE_INT(x);    
}

inline void FASTIO::WRITE_VAR(long long int x) {
  WRITE_INT(x);    
}

inline void FASTIO::WRITE_VAR(unsigned short int x) {
  WRITE_INT(x);    
}

inline void FASTIO::WRITE_VAR(unsigned int x) {
  WRITE_INT(x);    
}

inline void FASTIO::WRITE_VAR(unsigned long x) {
  WRITE_INT(x);    
}

inline void FASTIO::WRITE_VAR(unsigned long long x) {
  WRITE_INT(x);    
}

inline void FASTIO::WRITE_VAR(std::string &x) {
  WRITE_STRING(x);    
}

inline void FASTIO::WRITE_VAR(char x) {
  WRITE_CHAR(x);
}

inline void FASTIO::WRITE_VAR(const char *x) {
  WRITE_CHAR_ARRAY(x);
}

inline void FASTIO::WRITE_VAR(float x) {
  WRITE_FLOAT(x);
}

inline void FASTIO::WRITE_VAR(double x) {
  WRITE_DOUBLE(x);
}

inline void FASTIO::WRITE_VAR(long double x) {
  WRITE_DOUBLE(x);
}

template<std::size_t N>
inline void FASTIO::WRITE_VAR(std::bitset<N> &x) {
  WRITE_BITSET(x);
}  

컴파일 시 표준 에러 (stderr) 메시지

bridges.cpp:43: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
   43 | #pragma GCC optimization ("O3")
      | 
bridges.cpp:44: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
   44 | #pragma GCC optimization ("unroll-loops")
      | 
bridges.cpp: In function 'int main()':
bridges.cpp:160:7: warning: unused variable 'y' [-Wunused-variable]
  160 |   int y = queries[i].second ;
      |       ^
bridges.cpp:229:10: warning: unused variable 'a' [-Wunused-variable]
  229 |      int a = queries[ updates[k] ].first ;
      |          ^
bridges.cpp: In instantiation of 'void FASTIO::WRITE_INT(T) [with T = bool]':
bridges.cpp:479:14:   required from here
bridges.cpp:438:9: warning: comparison of constant '0' with boolean expression is always false [-Wbool-compare]
  438 |   if (x < 0) {putchar('-'); x = -x; }
      |       ~~^~~
bridges.cpp:121:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  121 |  scanf("%d%d", &N , &M ) ;
      |  ~~~~~^~~~~~~~~~~~~~~~~~
bridges.cpp:127:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  127 |   scanf("%d%d%d", &U[i], &V[i], &W[i] ) ;
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:131:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  131 |  scanf("%d", &Q ) ;
      |  ~~~~~^~~~~~~~~~~
bridges.cpp:135:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  135 |   scanf("%d%d%d", &t, &queries[i].first, &queries[i].second ) ;
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 13 / 13
• Subtask 2: 16 / 16
• Subtask 3: 17 / 17
• Subtask 4: 14 / 14
• Subtask 5: 13 / 13
• Subtask 6: 0 / 27