oj.uz

답안 #413409

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
413409 2021-05-28T16:54:20 Z arayi 다리 (APIO19_bridges) C++17
27 / 100
 412 ms 524292 KB 
//Arayi
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>
#include <queue>
#include <stack>
#include <algorithm>
#include <math.h>   
#include <vector>
#include <cstring>
#include <ctime>
#include <set>
#include <bitset>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <ctime>
#include <climits>
#include <cassert>
#include <chrono>
#include <random>
#include <complex>

#define fr first
#define sc second
#define MP make_pair
#define ad push_back
#define PB push_back
#define fastio ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define lli long long int
#define y1 arayikhalatyan
#define j1 jigglypuff
#define ld long double
#define itn int
#define pir pair<int, int>
#define all(x) (x).begin(), (x).end()
#define str string
#define enl endl
#define en endl
#define cd complex<long double>
#define vcd vector<cd>
#define vii vector<int>
#define vlli vector<lli>
using namespace std;

lli gcd(lli a, lli b) { return (b == 0LL ? a : gcd(b, a % b)); }
ld dist(ld x, ld y1, ld x2, ld y2)
{
    return sqrt((x - x2) * (x - x2) + (y1 - y2) * (y1 - y2));
}
lli S(lli a)
{
    return (a * (a + 1LL)) / 2;
}
mt19937 rnd(363542);
char vow[] = { 'a', 'e', 'i', 'o', 'u' };
int dx[] = { 0, -1, 0, 1, -1, -1, 1, 1, 0 };
int dy[] = { -1, 0, 1, 0, -1, 1, -1, 1, 0 };


const int N = 1e5 + 30;
const lli mod = 1e9 + 7;
const ld pi = acos(-1);
const int T = 500;

lli bp(lli a, lli b = mod - 2LL)
{
    lli ret = 1;
    while (b)
    {
        if (b & 1) ret *= a, ret %= mod;
        a *= a;
        a %= mod;
        b >>= 1;
    }
    return ret;
}
ostream& operator<<(ostream& c, pir a)
{
    c << a.fr << " " << a.sc;
    return c;
}
template<class T>
void maxi(T& a, T b)
{
    a = max(a, b);
}
template <class T>
void mini(T& a, T b)
{
    a = min(a, b);
}



int n, m, q, cl;
int a[N], b[N], c[N], pat[N], col[N];
int p[N / T + 3][N], sz[N / T + 3][N];
vector<pir> l[N / T + 3];
vector<pir> g[N / T + 3][N];
int gp(int i1, int x)
{
    if (p[i1][x] == x) return x;
    return p[i1][x] = gp(i1, p[i1][x]);
}
void lil(int i1, int a, int b)
{
    //cout << a << " " << b << endl;
    a = gp(i1, a), b = gp(i1, b);
    if (a == b) return;
    if (g[i1][a].size() < g[i1][b].size()) swap(a, b);
    for (auto p : g[i1][b]) g[i1][a].ad(p);
    g[i1][b].clear();
    if (sz[i1][a] > sz[i1][b]) p[i1][b] = a, sz[i1][a] += sz[i1][b];
    else p[i1][a] = b, sz[i1][b] += sz[i1][a], swap(g[i1][a], g[i1][b]);
}
int dfs(int i1, int v, int w)
{
    //cout << v << " ";
    v = gp(i1, v);
    //cout << v << endl;
    col[v] = cl;
    int ret = sz[i1][v];
    for (auto p : g[i1][v])
    {
        if (col[gp(i1, p.fr)] == cl || c[p.sc] < w) continue;
        ret += dfs(i1, p.fr, w);
    }
    return ret;
}
int main()
{
    fastio;
    cin >> n >> m;
    for (int i = 0; i < m; i++) cin >> a[i] >> b[i] >> c[i];
    for (int i = 0; i < 101; i++) 
        for (int j = 0; j <= n; j++) p[i][j] = j, sz[i][j] = 1;
    cin >> q;
    vector<pir> t;
    vector<pair<pir, pir> > fp;
    for (int i = 0; i < q; i++)
    {
        int A;
        cin >> A;
        if (A == 1)
        {
            int b, c;
            cin >> b >> c;
            t.ad(MP(c, b - 1));
        }
        else
        {
            int s, c;
            cin >> s >> c;
            fp.ad(MP(MP(c, s), MP(t.size(), i)));
        }
    }
    vector<pair<int, pir> > f;
    for (int i = 0; i < t.size(); i++)
    {
        if (i % T == 0)
        {
            unordered_set<int> s;
            for (int j = i; j < min(i + T, (int)t.size()); j++)
                s.insert(t[j].sc);
            for (int j = 0; j < m; j++)
            {
                if (s.find(j) != s.end()) l[i / T].ad(MP(j, c[j])), g[i / T][a[j]].ad(MP(b[j], j)), g[i / T][b[j]].ad(MP(a[j], j));
                else f.ad(MP(c[j], MP(j, i / T)));
            }
        }
        c[t[i].sc] = t[i].fr;
    }
    if ((int)t.size() % T == 0)
        for (int j = 0; j < m; j++) f.ad(MP(c[j], MP(j, (int)t.size() / T)));
    int i1 = 0;
    sort(all(fp)), sort(all(f));
    reverse(all(fp)), reverse(all(f));
    //for (auto p : f) cout << p.fr << " " << p.sc << endl;
    //for (auto p : fp) cout << p.fr << " " << p.sc << endl;
    for (int i = 0; i < fp.size(); i++)
    {
        while (i1 < f.size() && f[i1].fr >= fp[i].fr.fr)
        {
            lil(f[i1].sc.sc, a[f[i1].sc.fr], b[f[i1].sc.fr]);
            i1++;
        }
        int s = fp[i].fr.sc;
        int j = fp[i].sc.fr;
        int ii = j / T;
        for (auto p : l[ii]) c[p.fr] = p.sc;
        for (int k = ii * T; k < j; k++) c[t[k].sc] = t[k].fr;
        cl++;
        pat[fp[i].sc.sc] = dfs(ii, s, fp[i].fr.fr);
    }
    for (int i = 0; i < q; i++)
        if (pat[i]) cout << pat[i] << "\n";
    return 0;
}

/*
    __
  *(><)*
    \/ /
    ||/
  --||
    ||
    /\
   /  \
  /    \

*/

Compilation message

bridges.cpp: In function 'int main()':
bridges.cpp:160:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  160 |     for (int i = 0; i < t.size(); i++)
      |                     ~~^~~~~~~~~~
bridges.cpp:182:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  182 |     for (int i = 0; i < fp.size(); i++)
      |                     ~~^~~~~~~~~~~
bridges.cpp:184:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  184 |         while (i1 < f.size() && f[i1].fr >= fp[i].fr.fr)
      |                ~~~^~~~~~~~~~

Subtask #1
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 271 ms 478048 KB Output is correct
2 Correct 268 ms 478148 KB Output is correct
3 Correct 303 ms 478728 KB Output is correct
4 Correct 275 ms 478500 KB Output is correct
5 Correct 281 ms 478404 KB Output is correct
6 Correct 276 ms 478396 KB Output is correct
7 Correct 276 ms 478588 KB Output is correct
8 Correct 280 ms 478540 KB Output is correct
9 Correct 294 ms 478516 KB Output is correct
10 Correct 278 ms 478500 KB Output is correct
11 Correct 284 ms 478516 KB Output is correct
12 Correct 275 ms 478532 KB Output is correct
13 Correct 286 ms 478512 KB Output is correct
14 Correct 278 ms 478516 KB Output is correct
15 Correct 361 ms 478484 KB Output is correct
16 Correct 290 ms 478540 KB Output is correct
17 Correct 282 ms 478460 KB Output is correct

Subtask #2
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 307 ms 524292 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 302 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 391 ms 523976 KB Output is correct
2 Correct 329 ms 480488 KB Output is correct
3 Correct 316 ms 481436 KB Output is correct
4 Correct 314 ms 481440 KB Output is correct
5 Correct 375 ms 524128 KB Output is correct
6 Correct 412 ms 524020 KB Output is correct
7 Correct 377 ms 524076 KB Output is correct
8 Correct 366 ms 521832 KB Output is correct
9 Correct 372 ms 521912 KB Output is correct
10 Correct 372 ms 522304 KB Output is correct
11 Correct 377 ms 523280 KB Output is correct
12 Correct 382 ms 523436 KB Output is correct
13 Correct 384 ms 523452 KB Output is correct
14 Correct 380 ms 524288 KB Output is correct
15 Correct 376 ms 524116 KB Output is correct
16 Correct 391 ms 523804 KB Output is correct
17 Correct 394 ms 523768 KB Output is correct
18 Correct 409 ms 523984 KB Output is correct
19 Correct 388 ms 523936 KB Output is correct
20 Correct 383 ms 523760 KB Output is correct
21 Correct 392 ms 523760 KB Output is correct
22 Correct 392 ms 523064 KB Output is correct
23 Correct 376 ms 519528 KB Output is correct

Subtask #5
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 307 ms 524292 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 271 ms 478048 KB Output is correct
2 Correct 268 ms 478148 KB Output is correct
3 Correct 303 ms 478728 KB Output is correct
4 Correct 275 ms 478500 KB Output is correct
5 Correct 281 ms 478404 KB Output is correct
6 Correct 276 ms 478396 KB Output is correct
7 Correct 276 ms 478588 KB Output is correct
8 Correct 280 ms 478540 KB Output is correct
9 Correct 294 ms 478516 KB Output is correct
10 Correct 278 ms 478500 KB Output is correct
11 Correct 284 ms 478516 KB Output is correct
12 Correct 275 ms 478532 KB Output is correct
13 Correct 286 ms 478512 KB Output is correct
14 Correct 278 ms 478516 KB Output is correct
15 Correct 361 ms 478484 KB Output is correct
16 Correct 290 ms 478540 KB Output is correct
17 Correct 282 ms 478460 KB Output is correct
18 Runtime error 307 ms 524292 KB Execution killed with signal 9
19 Halted 0 ms 0 KB -