oj.uz

Submission #170107

# Submission time Handle Problem Language Result Execution time Memory
170107 2019-12-24T02:54:14 Z arnold518 Bridges (APIO19_bridges) C++14
100 / 100
 2904 ms 14524 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 1e5;

struct Edge
{
    int u, v, w, idx;
    bool operator < (const Edge &p) const { return w>p.w; }
};

struct Query
{
    int t, u, w, idx;
    bool operator < (const Query &p) const { return w>p.w; }
};

int N, M, Q, SQ=900;
int t[MAXN+10];
Edge edge[MAXN+10];
Query query[MAXN+10];

vector<int> S;
int Par[MAXN+10], Rank[MAXN+10];
vector<pii> ans;

void init()
{
    S.clear();
    for(int i=1; i<=N; i++) Par[i]=i, Rank[i]=1;
}

int cnt=0;

int Find(int x) { return x==Par[x] ? x : Find(Par[x]); }

void Union(int x, int y)
{
    x=Find(x); y=Find(y);
    if(x==y) return;
    if(Rank[x]<Rank[y]) swap(x, y);
    Rank[x]+=Rank[y];
    Par[y]=x;
    S.push_back(y);
    cnt++;
    //printf("UNION %d %d\n", x, y);
}

void Restore()
{
    if(S.empty()) return;
    //printf("RESTORE %d %d\n", S.back(), Par[S.back()]);
    Rank[Par[S.back()]]-=Rank[S.back()];
    Par[S.back()]=S.back();
    S.pop_back();
}

int main()
{
    int i, j, k, p;

    scanf("%d%d", &N, &M);
    for(i=1; i<=M; i++)
    {
        scanf("%d%d%d", &edge[i].u, &edge[i].v, &edge[i].w); edge[i].idx=i;
        if(edge[i].u>edge[i].v) swap(edge[i].u, edge[i].v);
    }
    scanf("%d", &Q);
    for(i=1; i<=Q; i++) scanf("%d%d%d", &query[i].t, &query[i].u, &query[i].w), query[i].idx=i;

    vector<Edge> E;
    for(i=1; i<=M; i++) E.push_back(edge[i]);
    sort(E.begin(), E.end());

    for(i=0; i<=Q/SQ; i++)
    {
        int s=max(1, i*SQ), e=min(Q, i*SQ+SQ-1);
        init();

        //printf("============\n");
        //for(auto it : E) printf("%d %d %d\n", it.u, it.v, it.w);
        //printf("============\n");

        vector<Edge> E1, E2;

        vector<Query> up, qu;
        vector<int> up2;
        for(j=s; j<=e; j++)
        {
            if(query[j].t==1) up.push_back(query[j]), up2.push_back(query[j].u);
            else qu.push_back(query[j]);
        }

        sort(up2.begin(), up2.end());
        up2.erase(unique(up2.begin(), up2.end()), up2.end());
        sort(qu.begin(), qu.end());

        for(j=0; j<E.size(); j++) if(!binary_search(up2.begin(), up2.end(), E[j].idx)) E1.push_back(E[j]);

        for(j=0, k=0; j<qu.size(); j++)
        {
            //printf("!!!!!!!!!!QUERY SOLVING %d %d!!!!!!!\n", qu[j].u, qu[j].w);
            for(; k<E.size() && E[k].w>=qu[j].w; k++)
            {
                if(binary_search(up2.begin(), up2.end(), E[k].idx)) continue;
                //printf("!%d %d\n", E[k].u, E[k].v);
                Union(E[k].u, E[k].v);
            }

            cnt=0;

            for(p=0; p<up2.size(); p++) t[up2[p]]=edge[up2[p]].w;
            for(p=0; p<up.size() && up[p].idx<qu[j].idx; p++) t[up[p].u]=up[p].w;
            for(p=0; p<up2.size(); p++) if(t[up2[p]]>=qu[j].w) Union(edge[up2[p]].u, edge[up2[p]].v);
            ans.push_back({qu[j].idx, Rank[Find(qu[j].u)]});
            while(cnt--) Restore();
        }

        //printf("!%d %d %d\n", E.size(), E1.size(), E2.size());

        for(p=0; p<up.size(); p++) edge[up[p].u].w=up[p].w;
        for(p=0; p<up2.size(); p++) E2.push_back(edge[up2[p]]);

        if(E1.size()+E2.size()!=M) while(1);

        sort(E2.begin(), E2.end());
        E.clear(); E.resize(M);
        merge(E1.begin(), E1.end(), E2.begin(), E2.end(), E.begin());
    }

    sort(ans.begin(), ans.end());
    for(auto it : ans) printf("%d\n", it.second);
}

Compilation message

bridges.cpp: In function 'int main()':
bridges.cpp:102:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(j=0; j<E.size(); j++) if(!binary_search(up2.begin(), up2.end(), E[j].idx)) E1.push_back(E[j]);
                  ~^~~~~~~~~
bridges.cpp:104:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(j=0, k=0; j<qu.size(); j++)
                       ~^~~~~~~~~~
bridges.cpp:107:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(; k<E.size() && E[k].w>=qu[j].w; k++)
                   ~^~~~~~~~~
bridges.cpp:116:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(p=0; p<up2.size(); p++) t[up2[p]]=edge[up2[p]].w;
                      ~^~~~~~~~~~~
bridges.cpp:117:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(p=0; p<up.size() && up[p].idx<qu[j].idx; p++) t[up[p].u]=up[p].w;
                      ~^~~~~~~~~~
bridges.cpp:118:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(p=0; p<up2.size(); p++) if(t[up2[p]]>=qu[j].w) Union(edge[up2[p]].u, edge[up2[p]].v);
                      ~^~~~~~~~~~~
bridges.cpp:125:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(p=0; p<up.size(); p++) edge[up[p].u].w=up[p].w;
                  ~^~~~~~~~~~
bridges.cpp:126:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(p=0; p<up2.size(); p++) E2.push_back(edge[up2[p]]);
                  ~^~~~~~~~~~~
bridges.cpp:128:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(E1.size()+E2.size()!=M) while(1);
            ~~~~~~~~~~~~~~~~~~~^~~
bridges.cpp:66:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &N, &M);
     ~~~~~^~~~~~~~~~~~~~~~
bridges.cpp:69:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d", &edge[i].u, &edge[i].v, &edge[i].w); edge[i].idx=i;
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:72:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &Q);
     ~~~~~^~~~~~~~~~
bridges.cpp:73:79: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(i=1; i<=Q; i++) scanf("%d%d%d", &query[i].t, &query[i].u, &query[i].w), query[i].idx=i;
                         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 35 ms 860 KB Output is correct
4 Correct 8 ms 872 KB Output is correct
5 Correct 18 ms 740 KB Output is correct
6 Correct 16 ms 760 KB Output is correct
7 Correct 19 ms 760 KB Output is correct
8 Correct 20 ms 888 KB Output is correct
9 Correct 22 ms 760 KB Output is correct
10 Correct 20 ms 760 KB Output is correct
11 Correct 20 ms 760 KB Output is correct
12 Correct 22 ms 760 KB Output is correct
13 Correct 25 ms 760 KB Output is correct
14 Correct 24 ms 760 KB Output is correct
15 Correct 21 ms 760 KB Output is correct
16 Correct 21 ms 756 KB Output is correct
17 Correct 20 ms 632 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1794 ms 7236 KB Output is correct
2 Correct 1978 ms 7548 KB Output is correct
3 Correct 1724 ms 7420 KB Output is correct
4 Correct 1755 ms 7480 KB Output is correct
5 Correct 1721 ms 7632 KB Output is correct
6 Correct 2291 ms 7244 KB Output is correct
7 Correct 2344 ms 7684 KB Output is correct
8 Correct 2321 ms 7548 KB Output is correct
9 Correct 57 ms 3296 KB Output is correct
10 Correct 1704 ms 7344 KB Output is correct
11 Correct 1669 ms 7388 KB Output is correct
12 Correct 1183 ms 8576 KB Output is correct
13 Correct 1624 ms 7080 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1375 ms 5868 KB Output is correct
2 Correct 945 ms 3444 KB Output is correct
3 Correct 1580 ms 6104 KB Output is correct
4 Correct 1375 ms 5924 KB Output is correct
5 Correct 57 ms 3296 KB Output is correct
6 Correct 1482 ms 6132 KB Output is correct
7 Correct 1235 ms 6028 KB Output is correct
8 Correct 1142 ms 5988 KB Output is correct
9 Correct 713 ms 6516 KB Output is correct
10 Correct 686 ms 6520 KB Output is correct
11 Correct 1201 ms 5332 KB Output is correct
12 Correct 983 ms 5400 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 735 ms 11256 KB Output is correct
2 Correct 59 ms 3168 KB Output is correct
3 Correct 136 ms 7676 KB Output is correct
4 Correct 120 ms 7948 KB Output is correct
5 Correct 706 ms 11400 KB Output is correct
6 Correct 710 ms 11244 KB Output is correct
7 Correct 707 ms 11464 KB Output is correct
8 Correct 387 ms 7876 KB Output is correct
9 Correct 386 ms 8184 KB Output is correct
10 Correct 387 ms 8492 KB Output is correct
11 Correct 597 ms 10200 KB Output is correct
12 Correct 577 ms 10200 KB Output is correct
13 Correct 601 ms 10340 KB Output is correct
14 Correct 723 ms 11600 KB Output is correct
15 Correct 728 ms 11728 KB Output is correct
16 Correct 764 ms 11616 KB Output is correct
17 Correct 764 ms 11460 KB Output is correct
18 Correct 767 ms 11484 KB Output is correct
19 Correct 750 ms 11616 KB Output is correct
20 Correct 668 ms 10940 KB Output is correct
21 Correct 658 ms 10976 KB Output is correct
22 Correct 737 ms 11428 KB Output is correct
23 Correct 608 ms 10760 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1794 ms 7236 KB Output is correct
2 Correct 1978 ms 7548 KB Output is correct
3 Correct 1724 ms 7420 KB Output is correct
4 Correct 1755 ms 7480 KB Output is correct
5 Correct 1721 ms 7632 KB Output is correct
6 Correct 2291 ms 7244 KB Output is correct
7 Correct 2344 ms 7684 KB Output is correct
8 Correct 2321 ms 7548 KB Output is correct
9 Correct 57 ms 3296 KB Output is correct
10 Correct 1704 ms 7344 KB Output is correct
11 Correct 1669 ms 7388 KB Output is correct
12 Correct 1183 ms 8576 KB Output is correct
13 Correct 1624 ms 7080 KB Output is correct
14 Correct 1375 ms 5868 KB Output is correct
15 Correct 945 ms 3444 KB Output is correct
16 Correct 1580 ms 6104 KB Output is correct
17 Correct 1375 ms 5924 KB Output is correct
18 Correct 57 ms 3296 KB Output is correct
19 Correct 1482 ms 6132 KB Output is correct
20 Correct 1235 ms 6028 KB Output is correct
21 Correct 1142 ms 5988 KB Output is correct
22 Correct 713 ms 6516 KB Output is correct
23 Correct 686 ms 6520 KB Output is correct
24 Correct 1201 ms 5332 KB Output is correct
25 Correct 983 ms 5400 KB Output is correct
26 Correct 1823 ms 7624 KB Output is correct
27 Correct 2223 ms 7168 KB Output is correct
28 Correct 1933 ms 7176 KB Output is correct
29 Correct 1538 ms 7264 KB Output is correct
30 Correct 2196 ms 7164 KB Output is correct
31 Correct 2207 ms 7156 KB Output is correct
32 Correct 2231 ms 7280 KB Output is correct
33 Correct 1921 ms 7032 KB Output is correct
34 Correct 1934 ms 7036 KB Output is correct
35 Correct 1954 ms 7500 KB Output is correct
36 Correct 1563 ms 7536 KB Output is correct
37 Correct 1569 ms 7164 KB Output is correct
38 Correct 1577 ms 7256 KB Output is correct
39 Correct 986 ms 8588 KB Output is correct
40 Correct 963 ms 8744 KB Output is correct
41 Correct 961 ms 8672 KB Output is correct
42 Correct 1344 ms 7312 KB Output is correct
43 Correct 1343 ms 7464 KB Output is correct
44 Correct 1329 ms 7540 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 35 ms 860 KB Output is correct
4 Correct 8 ms 872 KB Output is correct
5 Correct 18 ms 740 KB Output is correct
6 Correct 16 ms 760 KB Output is correct
7 Correct 19 ms 760 KB Output is correct
8 Correct 20 ms 888 KB Output is correct
9 Correct 22 ms 760 KB Output is correct
10 Correct 20 ms 760 KB Output is correct
11 Correct 20 ms 760 KB Output is correct
12 Correct 22 ms 760 KB Output is correct
13 Correct 25 ms 760 KB Output is correct
14 Correct 24 ms 760 KB Output is correct
15 Correct 21 ms 760 KB Output is correct
16 Correct 21 ms 756 KB Output is correct
17 Correct 20 ms 632 KB Output is correct
18 Correct 1794 ms 7236 KB Output is correct
19 Correct 1978 ms 7548 KB Output is correct
20 Correct 1724 ms 7420 KB Output is correct
21 Correct 1755 ms 7480 KB Output is correct
22 Correct 1721 ms 7632 KB Output is correct
23 Correct 2291 ms 7244 KB Output is correct
24 Correct 2344 ms 7684 KB Output is correct
25 Correct 2321 ms 7548 KB Output is correct
26 Correct 57 ms 3296 KB Output is correct
27 Correct 1704 ms 7344 KB Output is correct
28 Correct 1669 ms 7388 KB Output is correct
29 Correct 1183 ms 8576 KB Output is correct
30 Correct 1624 ms 7080 KB Output is correct
31 Correct 1375 ms 5868 KB Output is correct
32 Correct 945 ms 3444 KB Output is correct
33 Correct 1580 ms 6104 KB Output is correct
34 Correct 1375 ms 5924 KB Output is correct
35 Correct 57 ms 3296 KB Output is correct
36 Correct 1482 ms 6132 KB Output is correct
37 Correct 1235 ms 6028 KB Output is correct
38 Correct 1142 ms 5988 KB Output is correct
39 Correct 713 ms 6516 KB Output is correct
40 Correct 686 ms 6520 KB Output is correct
41 Correct 1201 ms 5332 KB Output is correct
42 Correct 983 ms 5400 KB Output is correct
43 Correct 735 ms 11256 KB Output is correct
44 Correct 59 ms 3168 KB Output is correct
45 Correct 136 ms 7676 KB Output is correct
46 Correct 120 ms 7948 KB Output is correct
47 Correct 706 ms 11400 KB Output is correct
48 Correct 710 ms 11244 KB Output is correct
49 Correct 707 ms 11464 KB Output is correct
50 Correct 387 ms 7876 KB Output is correct
51 Correct 386 ms 8184 KB Output is correct
52 Correct 387 ms 8492 KB Output is correct
53 Correct 597 ms 10200 KB Output is correct
54 Correct 577 ms 10200 KB Output is correct
55 Correct 601 ms 10340 KB Output is correct
56 Correct 723 ms 11600 KB Output is correct
57 Correct 728 ms 11728 KB Output is correct
58 Correct 764 ms 11616 KB Output is correct
59 Correct 764 ms 11460 KB Output is correct
60 Correct 767 ms 11484 KB Output is correct
61 Correct 750 ms 11616 KB Output is correct
62 Correct 668 ms 10940 KB Output is correct
63 Correct 658 ms 10976 KB Output is correct
64 Correct 737 ms 11428 KB Output is correct
65 Correct 608 ms 10760 KB Output is correct
66 Correct 1823 ms 7624 KB Output is correct
67 Correct 2223 ms 7168 KB Output is correct
68 Correct 1933 ms 7176 KB Output is correct
69 Correct 1538 ms 7264 KB Output is correct
70 Correct 2196 ms 7164 KB Output is correct
71 Correct 2207 ms 7156 KB Output is correct
72 Correct 2231 ms 7280 KB Output is correct
73 Correct 1921 ms 7032 KB Output is correct
74 Correct 1934 ms 7036 KB Output is correct
75 Correct 1954 ms 7500 KB Output is correct
76 Correct 1563 ms 7536 KB Output is correct
77 Correct 1569 ms 7164 KB Output is correct
78 Correct 1577 ms 7256 KB Output is correct
79 Correct 986 ms 8588 KB Output is correct
80 Correct 963 ms 8744 KB Output is correct
81 Correct 961 ms 8672 KB Output is correct
82 Correct 1344 ms 7312 KB Output is correct
83 Correct 1343 ms 7464 KB Output is correct
84 Correct 1329 ms 7540 KB Output is correct
85 Correct 2815 ms 11748 KB Output is correct
86 Correct 321 ms 7944 KB Output is correct
87 Correct 196 ms 8232 KB Output is correct
88 Correct 2089 ms 10792 KB Output is correct
89 Correct 2804 ms 10984 KB Output is correct
90 Correct 1965 ms 10784 KB Output is correct
91 Correct 1995 ms 7316 KB Output is correct
92 Correct 1972 ms 7292 KB Output is correct
93 Correct 2716 ms 7440 KB Output is correct
94 Correct 2336 ms 9728 KB Output is correct
95 Correct 2407 ms 9592 KB Output is correct
96 Correct 2086 ms 9632 KB Output is correct
97 Correct 1284 ms 11820 KB Output is correct
98 Correct 1825 ms 10260 KB Output is correct
99 Correct 2824 ms 11108 KB Output is correct
100 Correct 2816 ms 10928 KB Output is correct
101 Correct 2875 ms 10944 KB Output is correct
102 Correct 2904 ms 14524 KB Output is correct
103 Correct 2241 ms 13016 KB Output is correct
104 Correct 2153 ms 13012 KB Output is correct
105 Correct 1934 ms 12376 KB Output is correct
106 Correct 1706 ms 11716 KB Output is correct
107 Correct 1420 ms 14012 KB Output is correct
108 Correct 2195 ms 13792 KB Output is correct
109 Correct 1885 ms 11652 KB Output is correct