제출 #164172

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
164172		arnold518	Collapse (JOI18_collapse)	C++14	0 / 100	48 ms	7156 KiB

collapse

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

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

const int MAXN = 2e5;
const int SQ = 330;

struct Query { int t, x, y, s; };

int N, C, Q, M;
int T[MAXN+10], X[MAXN+10], Y[MAXN+10], W[MAXN+10], P[MAXN+10], ans[MAXN+10];
Query U[MAXN+10];

int Par[MAXN+10], Rank[MAXN+10];
int Find(int x) { return x==Par[x] ? x : Find(Par[x]); }

vector<Query> query;

vector<int> simulateCollapse(int _N, vector<int> _T, vector<int> _X, vector<int> _Y, vector<int> _W, vector<int> _P)
{
    int i, j, k;
    N=_N; C=_T.size(); Q=_W.size(); M=C+Q;

    for(i=1; i<=C; i++) T[i]=_T[i-1], X[i]=_X[i-1]+1, Y[i]=_Y[i-1]+1;
    for(i=1; i<=C; i++) if(X[i]>Y[i]) swap(X[i], Y[i]);
    for(i=1; i<=Q; i++) W[i]=_W[i-1]+1, P[i]=_P[i-1]+1;
    for(i=1; i<=Q; i++) U[i]={W[i], P[i], i};
    sort(U+1, U+Q+1, [&](const Query &p, const Query &q) { return p.t<q.t; });

    for(i=1, j=1; i<=C; i++)
    {
        query.push_back({T[i], X[i], Y[i], query.size()});
        for(; U[j].t<=i && j<=Q; j++) query.push_back({-1, U[j].x, U[j].y, query.size()});
    }
    //for(auto it : query) printf("QUERY %d %d %d %d\n", it.t, it.x, it.y, it.s);

    set<pii> alive;
    for(i=0; i<=M/SQ; i++)
    {
        int s=i*SQ, e=min(M, (i+1)*SQ);

        int it, jt;
        vector<pii> edge;
        vector<Query> upd, ask;

        for(auto it : alive) edge.push_back(it);
        for(j=s; j<e; j++)
        {
            if(query[j].t==-1) ask.push_back(query[j]);
            else upd.push_back(query[j]);
        }

        sort(edge.begin(), edge.end(), [&](const pii &p, const pii &q) { return p.second<q.second; });
        sort(ask.begin(), ask.end(), [&](const Query &p, const Query &q) { return p.x<q.x; });

        for(j=1; j<=N; j++) Par[j]=j, Rank[j]=1;
        int cnt=0;

        it=0, jt=0;
        for(j=1; j<=N; j++)
        {
            for(; it<edge.size() && edge[it].second<=j; it++)
            {
                int u=edge[it].first, v=edge[it].second;
                u=Find(u); v=Find(v);
                if(u==v) continue;
                if(Rank[u]<Rank[v]) swap(u, v);
                Rank[u]+=Rank[v]; Par[v]=u;
                cnt++;
            }

            //printf("!%d\n", cnt);
            for(; jt<ask.size() && ask[jt].x<=j; jt++)
            {
                vector<int> S;
                for(k=0; k<upd.size(); k++)
                {
                    if(upd[k].s>=ask[jt].s) continue;
                    if(upd[k].y>j) continue;
                    int u=upd[k].x, v=upd[k].y;
                    u=Find(u); v=Find(v);
                    if(u==v) continue;
                    if(Rank[u]<Rank[v]) swap(u, v);
                    Rank[u]+=Rank[v]; Par[v]=u;
                    cnt++; S.push_back(v);
                }

                ans[ask[jt].y]+=cnt;
                //printf("! %d !%d %d\n", ask[jt].x, j, cnt);

                while(!S.empty())
                {
                    int now=S.back();
                    Rank[Par[now]]-=Rank[now];
                    Par[now]=now;
                    cnt--; S.pop_back();
                }
            }
        }

        sort(edge.begin(), edge.end(), [&](const pii &p, const pii &q) { return p.first>q.first; });
        sort(ask.begin(), ask.end(), [&](const Query &p, const Query &q) { return p.x>q.x; });

        for(j=1; j<=N; j++) Par[j]=j, Rank[j]=1;
        cnt=0;

        it=0, jt=0;
        for(j=N; j>=1; j--)
        {
            for(; it<edge.size() && edge[it].first>=j; it++)
            {
                int u=edge[it].first, v=edge[it].second;
                u=Find(u); v=Find(v);
                if(Rank[u]<Rank[v]) swap(u, v);
                Rank[u]+=Rank[v]; Par[v]=u;
                cnt++;
            }

            //printf("!%d\n", cnt);
            for(; jt<ask.size() && ask[jt].x+1>=j; jt++)
            {
                vector<int> S;
                for(k=0; k<upd.size(); k++)
                {
                    if(upd[k].s>=ask[jt].s) continue;
                    if(upd[k].x<j) continue;
                    int u=upd[k].x, v=upd[k].y;
                    u=Find(u); v=Find(v);
                    if(u==v) continue;
                    if(Rank[u]<Rank[v]) swap(u, v);
                    Rank[u]+=Rank[v]; Par[v]=u;
                    cnt++; S.push_back(v);
                }

                ans[ask[jt].y]+=cnt;
                //printf("!!%d %d\n", j, cnt);

                while(!S.empty())
                {
                    int now=S.back();
                    Rank[Par[now]]-=Rank[now];
                    Par[now]=now;
                    cnt--; S.pop_back();
                }
            }
        }

        for(j=0; j<upd.size(); j++) alive.insert({upd[j].x, upd[j].y});
    }

    for(i=1; i<=Q; i++) ans[i]=N-ans[i];
    return vector<int>(ans+1, ans+Q+1);
}

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

collapse.cpp: In function 'std::vector<int> simulateCollapse(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
collapse.cpp:36:54: warning: narrowing conversion of 'query.std::vector<Query>::size()' from 'std::vector<Query>::size_type {aka long unsigned int}' to 'int' inside { } [-Wnarrowing]
         query.push_back({T[i], X[i], Y[i], query.size()});
                                            ~~~~~~~~~~^~
collapse.cpp:37:86: warning: narrowing conversion of 'query.std::vector<Query>::size()' from 'std::vector<Query>::size_type {aka long unsigned int}' to 'int' inside { } [-Wnarrowing]
         for(; U[j].t<=i && j<=Q; j++) query.push_back({-1, U[j].x, U[j].y, query.size()});
                                                                            ~~~~~~~~~~^~
collapse.cpp:66:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(; it<edge.size() && edge[it].second<=j; it++)
                   ~~^~~~~~~~~~~~
collapse.cpp:77:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(; jt<ask.size() && ask[jt].x<=j; jt++)
                   ~~^~~~~~~~~~~
collapse.cpp:80:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 for(k=0; k<upd.size(); k++)
                          ~^~~~~~~~~~~
collapse.cpp:114:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(; it<edge.size() && edge[it].first>=j; it++)
                   ~~^~~~~~~~~~~~
collapse.cpp:124:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(; jt<ask.size() && ask[jt].x+1>=j; jt++)
                   ~~^~~~~~~~~~~
collapse.cpp:127:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 for(k=0; k<upd.size(); k++)
                          ~^~~~~~~~~~~
collapse.cpp:152:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(j=0; j<upd.size(); j++) alive.insert({upd[j].x, upd[j].y});
                  ~^~~~~~~~~~~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 30
• Subtask 3: 0 / 30
• Subtask 4: 0 / 35