oj.uz

답안 #169481

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
169481 2019-12-20T15:30:17 Z Andrei_Cotor Pipes (CEOI15_pipes) C++14
50 / 100
 1700 ms 33880 KB 
#include<iostream>
#include<vector>
#include<stdlib.h>

using namespace std;

int ParLink[100005],P[100005],Lev[100005],Sz[100005],Low[100005],Covered[100005],Prv[100005],SzLink[100005];
pair<int,int> Edge[100005];
vector<pair<int,int> > A[100005];

int parentLink(int x)
{
    int cx=x;
    while(ParLink[x]!=0)
        x=ParLink[x];

    while(ParLink[cx]!=0)
    {
        int aux=ParLink[cx];
        ParLink[cx]=x;
        cx=aux;
    }
    return x;
}

void uniLink(int x, int y)
{
    x=parentLink(x);
    y=parentLink(y);

    if(x==y)
        return;

    if(SzLink[x]>SzLink[y])
    {
        SzLink[x]+=SzLink[y];
        ParLink[y]=x;
        if(Lev[Low[y]]<Lev[Low[x]])
            Low[x]=Low[y];
    }
    else
    {
        SzLink[y]+=SzLink[x];
        ParLink[x]=y;
        if(Lev[Low[x]]<Lev[Low[y]])
            Low[y]=Low[x];
    }
}

void dfs(int nod, int p, int lev, int px)
{
    P[nod]=px;
    Lev[nod]=lev;
    for(auto other:A[nod])
        if(other.first!=p)
        {
            Prv[other.first]=other.second;
            dfs(other.first,nod,lev+1,px);
            Low[parentLink(other.second)]=nod;
        }
}

void unite(int x, int y, int nr)
{
    int px=P[x];
    int py=P[y];
    if(Sz[px]<Sz[py])
    {
        swap(x,y);
        swap(px,py);
    }

    Sz[px]+=Sz[py];

    A[x].push_back({y,nr});
    A[y].push_back({x,nr});
    if(A[x].size()>100000 || A[y].size()>100000)
        exit(0);

    Prv[y]=nr;
    Low[nr]=x;
    ParLink[nr]=0;
    SzLink[nr]=1;
    dfs(y,x,Lev[x]+1,px);
}

void update(int x, int y)
{
    int prvLinkx=0;
    int prvLinky=0;
    while(x!=y)
    {
        if(Lev[x]<Lev[y])
        {
            swap(x,y);
            swap(prvLinkx,prvLinky);
        }

        Covered[Prv[x]]=1;

        if(prvLinkx!=0)
            uniLink(Prv[x],prvLinkx);

        prvLinkx=Prv[x];
        x=Low[parentLink(Prv[x])];
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n,m;
    cin>>n>>m;
    for(int i=1; i<=n; i++)
    {
        Sz[i]=1;
        P[i]=i;
        Lev[i]=1;
    }

    int nr=0;
    for(int i=1; i<=m; i++)
    {
        int x,y;
        cin>>x>>y;
        if(P[x]!=P[y])
        {
            nr++;
            Edge[nr]={x,y};
            unite(x,y,nr);
        }
        else
            update(x,y);
    }

    for(int i=1; i<=nr; i++)
        if(!Covered[i])
            cout<<Edge[i].first<<" "<<Edge[i].second<<"\n";
    return 0;
}

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 4 ms 2680 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 3192 KB Output is correct
2 Correct 8 ms 3192 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 132 ms 4604 KB Output is correct
2 Correct 130 ms 3960 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 235 ms 4600 KB Output is correct
2 Correct 264 ms 4764 KB Output is correct

Subtask #5
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 417 ms 5624 KB Output is correct
2 Runtime error 347 ms 18808 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)

Subtask #6
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 549 ms 8568 KB Output is correct
2 Runtime error 508 ms 26160 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 849 ms 10464 KB Output is correct
2 Correct 840 ms 10232 KB Output is correct

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1117 ms 11768 KB Output is correct
2 Runtime error 1089 ms 18700 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1428 ms 11388 KB Output is correct
2 Runtime error 1393 ms 20472 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)

Subtask #10
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1700 ms 10020 KB Output is correct
2 Runtime error 1685 ms 33880 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)