Submission #1243587

#	Time	Username	Problem	Language	Result	Execution time	Memory
1243587		sitingfake	Bridges (APIO19_bridges)	C++20	100 / 100	2715 ms	110404 KiB

bridges

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

// define
#define FIO
struct IO {
#ifdef FIO
    const static int BUFSIZE = 1 << 20;
    char buf[BUFSIZE], obuf[BUFSIZE], *p1, *p2, *pp;
    inline char getchar() {
        return (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, BUFSIZE, stdin), p1 == p2) ? EOF : *p1++);
    }
    inline void putchar(char x) {
        ((pp - obuf == BUFSIZE && (fwrite(obuf, 1, BUFSIZE, stdout), pp = obuf)), *pp = x, pp++);
    }
    inline IO &flush() {
        fwrite(obuf, 1, pp - obuf, stdout);
        fflush(stdout);
        return *this;
    }
    IO() {
        p1 = buf, p2 = buf, pp = obuf;
    }
    ~IO() {
        flush();
    }
#else
    int (*getchar)() = &::getchar;
    int (*putchar)(int) = &::putchar;
    inline IO &flush() {
        fflush(stdout);
        return *this;
    };
#endif
    string sep = " ";
    int k = 2;
    template < typename Tp, typename std::enable_if < std::is_integral<Tp>::value | std::is_same<Tp, __int128_t>::value >::type * = nullptr >
    inline int read(Tp &s) {
        int f = 1;
        char ch = getchar();
        s = 0;
        while (!isdigit(ch) && ch != EOF)    f = (ch == '-' ? -1 : 1), ch = getchar();
        while (isdigit(ch))        s = s * 10 + (ch ^ 48), ch = getchar();
        s *= f;
        return ch != EOF;
    }
    template<typename Tp, typename enable_if<is_floating_point<Tp>::value>::type * = nullptr>
    inline int read(Tp &s) {
        int f = 1;
        char ch = getchar();
        s = 0;
        while (!isdigit(ch) && ch != EOF && ch != '.')    f = (ch == '-' ? -1 : 1), ch = getchar();
        while (isdigit(ch))        s = s * 10 + (ch ^ 48), ch = getchar();
        if(ch == EOF)    return false;
        if(ch == '.') {
            Tp eps = 0.1;
            ch = getchar();
            while (isdigit(ch))        s = s + (ch ^ 48) * eps, ch = getchar(), eps /= 10;
        }
        s *= f;
        return ch != EOF;
    }
    inline int read(char &c) {
        char ch = getchar();
        c = EOF;
        while(isspace(ch) && ch != EOF)     ch = getchar();
        if(ch != EOF) c = ch;
        return c != EOF;
    }
    inline int read(char *c) {
        char ch = getchar(), *s = c;
        while(isspace(ch) && ch != EOF)     ch = getchar();
        while(!isspace(ch) && ch != EOF)    *(c++) = ch, ch = getchar();
        *c = '\0';
        return s != c;
    }
    inline int read(string &s) {
        s.clear();
        char ch = getchar();
        while(isspace(ch) && ch != EOF)     ch = getchar();
        while(!isspace(ch) && ch != EOF)    s += ch, ch = getchar();
        return s.size() > 0;
    }
    inline int getline(char *c, const char &ed = '\n') {
        char ch = getchar(), *s = c;
        while(ch != ed && ch != EOF)        *(c++) = ch, ch = getchar();
        *c = '\0';
        return s != c;
    }
    inline int getline(string &s, const char &ed = '\n') {
        s.clear();
        char ch = getchar();
        while(ch != ed && ch != EOF)        s += ch, ch = getchar();
        return s.size() > 0;
    }
    template<typename Tp = int>
    inline Tp read() {
        Tp x;
        read(x);
        return x;
    }
    template<typename Tp, typename... Ts>
    int read(Tp &x, Ts &...val) {
        return read(x) && read(val...);
    }
    template<typename Tp, typename enable_if<is_integral<Tp>::value>::type * = nullptr>
    IO & write(Tp x) {
        if (x < 0)    putchar('-'), x = -x;
        static char sta[20];
        int top = 0;
        do sta[top++] = x % 10 + '0', x /= 10;
        while (x);
        while (top)
            putchar(sta[--top]);
        return *this;
    }
    inline IO &write(const string &str) {
        for(char ch : str)    putchar(ch);
        return *this;
    }
    inline IO &write(const char *str) {
        while(*str != '\0')    putchar(*(str++));
        return *this;
    }
    inline IO &write(char *str) {
        return write((const char *)str);
    }
    inline IO &write(const char &ch) {
        return putchar(ch), *this;
    }
    template<typename Tp, typename enable_if<is_floating_point<Tp>::value>::type * = nullptr>
    inline IO & write(Tp x) {
        if(x > 1e18 || x < -1e18) {
            write("[Floating point overflow]");
            throw;
        }
        if(x < 0)    putchar('-'), x = -x;
        const static long long pow10[] = {1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000, 10000000000, 100000000000, 1000000000000, 10000000000000, 100000000000000, 1000000000000000, 10000000000000000, 100000000000000000, 100000000000000000, 100000000000000000};
        const auto &n = pow10[k];
        long long whole = (int)x;
        double tmp = (x - whole) * n;
        long long frac = tmp;
        double diff = tmp - frac;
        if (diff > 0.5) {
            ++frac;
            if (frac >= n)    frac = 0, ++whole;
        } else if (diff == 0.5 && ((frac == 0U) || (frac & 1U))) ++frac;
        write(whole);
        if (k == 0U) {
            diff = x - (double)whole;
            if ((!(diff < 0.5) || (diff > 0.5)) && (whole & 1))
                ++whole;
        } else {
            putchar('.');
            static char sta[20];
            int count = k, top = 0;
            while (frac) {
                sta[top++] = frac % 10 + '0';
                frac /= 10, count--;
            }
            while (count--) putchar('0');
            while (top) putchar(sta[--top]);
        }
        return *this;
    }
    template<typename Tp, typename... Ts>
    inline IO &write(Tp x, Ts... val) {
        write(x);
        write(sep);
        write(val...);
        return *this;
    }
    template<typename... Ts>
    inline IO &writeln(Ts... val) {
        write(val...);
        putchar('\n');
        return *this;
    }
    inline IO &writeln(void) {
        putchar('\n');
        return *this;
    }
    template<typename Tp>
    inline IO &writeWith(Tp x, const string &s = " ") {
        write(x), write(s);
        return *this;
    }
    inline IO &setsep(const string &s) {
        return sep = s, *this;
    }
    inline IO &setprec(const int &K) {
        return k = K, *this;
    }
} io;

static struct FastInput {
  static constexpr int BUF_SIZE = 1 << 20;
  char buf[BUF_SIZE];
  size_t chars_read = 0;
  size_t buf_pos = 0;
  FILE *in = stdin;
  char cur = 0;

  inline char get_char() {
    if (buf_pos >= chars_read) {
      chars_read = fread(buf, 1, BUF_SIZE, in);
      buf_pos = 0;
      buf[0] = (chars_read == 0 ? -1 : buf[0]);
    }
    return cur = buf[buf_pos++];
  }

  inline void tie(int) {}

  inline explicit operator bool() {
    return cur != -1;
  }

  inline static bool is_blank(char c) {
    return c <= ' ';
  }

  inline bool skip_blanks() {
    while (is_blank(cur) && cur != -1) {
      get_char();
    }
    return cur != -1;
  }

  inline FastInput& operator>>(char& c) {
    skip_blanks();
    c = cur;
    return *this;
  }

  inline FastInput& operator>>(string& s) {
    if (skip_blanks()) {
      s.clear();
      do {
        s += cur;
      } while (!is_blank(get_char()));
    }
    return *this;
  }

  template <typename T>
  inline FastInput& read_integer(T& n) {
    // unsafe, doesn't check that characters are actually digits
    n = 0;
    if (skip_blanks()) {
      int sign = +1;
      if (cur == '-') {
        sign = -1;
        get_char();
      }
      do {
        n += n + (n << 3) + cur - '0';
      } while (!is_blank(get_char()));
      n *= sign;
    }
    return *this;
  }

  template <typename T>
  inline typename enable_if<is_integral<T>::value, FastInput&>::type operator>>(T& n) {
    return read_integer(n);
  }

  #if !defined(_WIN32) || defined(_WIN64)
  inline FastInput& operator>>(__int128& n) {
    return read_integer(n);
  }
  #endif

  template <typename T>
  inline typename enable_if<is_floating_point<T>::value, FastInput&>::type operator>>(T& n) {
    // not sure if really fast, for compatibility only
    n = 0;
    if (skip_blanks()) {
      string s;
      (*this) >> s;
      sscanf(s.c_str(), "%lf", &n);
    }
    return *this;
  }
} fast_input;

#define cin fast_input

static struct FastOutput {
  static constexpr int BUF_SIZE = 1 << 20;
  char buf[BUF_SIZE];
  size_t buf_pos = 0;
  static constexpr int TMP_SIZE = 1 << 20;
  char tmp[TMP_SIZE];
  FILE *out = stdout;

  inline void put_char(char c) {
    buf[buf_pos++] = c;
    if (buf_pos == BUF_SIZE) {
      fwrite(buf, 1, buf_pos, out);
      buf_pos = 0;
    }
  }

  ~FastOutput() {
    fwrite(buf, 1, buf_pos, out);
  }

  inline FastOutput& operator<<(char c) {
    put_char(c);
    return *this;
  }

  inline FastOutput& operator<<(const char* s) {
    while (*s) {
      put_char(*s++);
    }
    return *this;
  }

  inline FastOutput& operator<<(const string& s) {
    for (int i = 0; i < (int) s.size(); i++) {
      put_char(s[i]);
    }
    return *this;
  }

  template <typename T>
  inline char* integer_to_string(T n) {
    // beware of TMP_SIZE
    char* p = tmp + TMP_SIZE - 1;
    if (n == 0) {
      *--p = '0';
    } else {
      bool is_negative = false;
      if (n < 0) {
        is_negative = true;
        n = -n;
      }
      while (n > 0) {
        *--p = (char) ('0' + n % 10);
        n /= 10;
      }
      if (is_negative) {
        *--p = '-';
      }
    }
    return p;
  }

  template <typename T>
  inline typename enable_if<is_integral<T>::value, char*>::type stringify(T n) {
    return integer_to_string(n);
  }

  #if !defined(_WIN32) || defined(_WIN64)
  inline char* stringify(__int128 n) {
    return integer_to_string(n);
  }
  #endif

  template <typename T>
  inline typename enable_if<is_floating_point<T>::value, char*>::type stringify(T n) {
    sprintf(tmp, "%.17f", n);
    return tmp;
  }

  template <typename T>
  inline FastOutput& operator<<(const T& n) {
    auto p = stringify(n);
    for (; *p != 0; p++) {
      put_char(*p);
    }
    return *this;
  }
} fast_output;
#define cout fast_output
#define execute cerr << " Time: " << fixed << setprecision(6) << (1.0 * clock() / CLOCKS_PER_SEC) << "s\n";
#define ll long long
#define ld double
#define ii pair<int,int>
#define se second
#define fi first
#define iii pair<int,ii>
#define all(v) v.begin(),v.end()
#define bit(x,i) (((x)>>(i))&1LL)
#define flip(x,i) ((x)^(1LL<<(i)))
#define ms(d,x) memset(d,x,sizeof(d))
#define sitingfake 1
#define orz 1
#define exist __exist
#define ends __ends
#define visit visited
#define left __left
#define right __right

//constant

const ll mod = 1e9 + 7;
const long long linf = 4557430888798830399;
const int inf = 1061109567;
const int maxarr = 1e6 + 5;
int dx[] = {0 , -1 , 0 , 1};
int dy[] = {-1 , 0 , 1 , 0};

template<typename T> bool maximize(T &a, const T &b)
{
    if(a < b) {a = b; return 1;}
    return 0;
}

template<typename T> bool minimize(T &a, const T &b)
{
    if(a > b) {a = b; return 1;}
    return 0;
}

inline void Plus(ll & a ,ll b)
{
    b %= mod;
    a += b;
    if(a >= mod) a -= mod;
    if(a < 0) a += mod;
    return;
}

inline void Mul(ll & a, ll b)
{
    a %= mod; b %= mod;
    a *= b;
    a %= mod;
    return;
}

//code

const int maxn = 1e5 + 7;

int n , m;

int q;

int NumBlocks , Lim;

int ans[maxn];

iii edges[maxn];

bool changed[maxn];

vector <ii> E[maxn];

struct query
{
    int type;
    int u;
    int w;
    int i;
};

struct Event
{
    int t;
    // 0 -> dsu , 1 -> query
    int w;
    int u;
    int v;
    int id;

    bool operator < (Event & other)
    {
        if(w == other.w) return t < other.t;
        return w > other.w;
    }
};

vector <query> Q[505];

struct Dsu
{
    vector <int> par , sz;

    struct Info
    {
        int u;
        int PrePar;
        int PreSize;
        bool type;
        // 0 -> adjust parent , 1 -> adjust size
    };

    stack <Info> st;

    int num;

    Dsu(int n)
    {
        num = n;
        par = vector <int>(n + 2);
        sz = vector <int> (n + 2 , 1);

        for(int i = 1; i <= num; i++)
        {
            par[i] = i;
        }
    }

    int get(int u)
    {
        while(par[u] != u) u = par[u];
        return u;
    }

    int getsize(int u)
    {
        u = get(u);
        return sz[u];
    }

    bool uni(int u ,int v , bool save)
    {
        u = get(u);
        v = get(v);
        if(u == v) return 0;

        if(sz[u] < sz[v]) swap(u , v);

        if(save)
        {
            st.push({v , par[v] , 0 , 0});
            st.push({u , 0 , sz[u] , 1});
        }

        sz[u] += sz[v];
        par[v] = u;

        return 1;
    }

    void RollBack(int target)
    {
        while(st.size() > target)
        {
            Info tmp = st.top();
            st.pop();

            if(tmp.type)
            {
                sz[tmp.u] = tmp.PreSize;
            }
            else
            {
                par[tmp.u] = tmp.PrePar;
            }
        }
    }

    void Reset()
    {
        while(!st.empty()) st.pop();
        for(int i = 1; i <= num; i++)
        {
            par[i] = i;
            sz[i] = 1;
        }
    }
};

void solve(void)
{
    cin >> n >> m;

    for(int i = 1; i <= m; i++)
    {
        cin >> edges[i].se.fi >> edges[i].se.se >> edges[i].fi;
    }

    cin >> q;

    Lim = 400;
    NumBlocks = (q + Lim - 1) / Lim;

    for(int i = 1; i <= q; i++)
    {
        int id = (i + Lim - 1) / Lim;
        query tmp;

        cin >> tmp.type >> tmp.u >> tmp.w;
        tmp.i = i;

        Q[id].push_back(tmp);
    }

    Dsu dsu(n);

    ms(ans , -1);
    vector <Event> tmp;

    for(int i = 1; i <= NumBlocks; i++)
    {
        for(int j = 0; j < Q[i].size(); j++)
        {
            query it = Q[i][j];

            if(it.type == 1)
            {
                changed[it.u] = 1;
                edges[it.u].fi = it.w;
            }
            else
            {
                tmp.push_back({1 , it.w , it.u , 0 , it.i});

                for(int k = 0; k < Q[i].size(); k++)
                {
                    if(k == j || Q[i][k].type == 2) continue;

                    int val = edges[Q[i][k].u].fi;

                    if(val >= it.w) E[it.i].push_back(edges[Q[i][k].u].se);
                }
            }
        }

        for(int j = 1; j <= m; j++)
        {
            if(!changed[j])
            {
                tmp.push_back({0 , edges[j].fi , edges[j].se.fi , edges[j].se.se , 0});
            }
        }

        sort(all(tmp));

        for(Event it : tmp)
        {
            if(it.t == 0)
            {
                dsu.uni(it.u , it.v , 0);
            }
            else
            {

                for(ii e : E[it.id])
                {
                    dsu.uni(e.fi , e.se , 1);
                }
                ans[it.id] = dsu.getsize(it.u);

                dsu.RollBack(0);
            }
        }

        for(query it : Q[i])
        {
            if(it.type == 1)
            {
                changed[it.u] = 0;
            }
        }

        dsu.Reset();
        tmp.clear();
    }

    for(int i = 1; i <= q; i++)
    {
        if(ans[i] != -1) cout << ans[i] << "\n";
    }
}


/**
7 8
1 2 5
1 6 5
2 3 5
2 7 5
3 4 5
4 5 5
5 6 5
6 7 5
3
2 1 6
1 1 1
2 1 2
**/
signed main()
{
   ios_base::sync_with_stdio(0);
   cin.tie(0);
//   cout.tie(0);

   #define task ""

   if(fopen(task".inp","r"))
   {
       freopen(task".inp","r",stdin);
       freopen(task".out","w",stdout);
   }

   int tc; tc = 1;

   while(tc--) solve();

   //execute;
}

Compilation message (stderr)

bridges.cpp: In function 'int main()':
bridges.cpp:699:15: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  699 |        freopen(task".inp","r",stdin);
      |        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:700:15: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  700 |        freopen(task".out","w",stdout);
      |        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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