oj.uz

Submission #12804

# Submission time Handle Problem Language Result Execution time Memory
12804 2015-01-03T16:07:21 Z woqja125 전선 연결하기 (GA9_wire) C++14
0 / 100
 0 ms 8240 KB 
#include<stdio.h>
#include<set>
int d[600001];
int l[300001];
int ans[300001];
int p[300001], e[300001];
struct R
{
    int s, e, n;
    R(int _s, int _e, int _n):s(_s), e(_e), n(_n){}
};
bool operator<(const R &A, const R &B){return A.s<B.s;}
int root(int x){return p[x]==x?x:p[x]=root(p[x]);}
int uni(int a, int b){a=root(a);b=root(b);return p[b] = a;}
void chk(int a, int b)
{
    a = root(a);
    b = root(b);
    if(e[a] != 0) uni(e[a], b);
    if(e[b] != 0) a = uni(e[b], a);
    e[a] = b = root(b);
    e[b] = a;
}
int main()
{
    int n, i;
    int t;
    scanf("%d", &n);
    for(i=1; i<=n; i++) p[i] = i;
    for(i=1; i<=2*n; i++)
    {
        scanf("%d", d+i);
        l[d[i]] = i;
    }
    std::set<R> S;
    for(i=1; i<=2*n; i++)
    {
        t = l[d[i]];
        if(t == i) continue;
        int s, end;
        s=10000000; end = -1;
        while(!S.empty() && S.begin()->e <= i) S.erase(S.begin());
        auto it = S.begin();
        for(; it != S.end() && it->s <= t; it=S.begin())
        {
            if(s > it->s) s = it->s;
            if(end < it->e) end = it->e;
//            printf("! %d %d\n", d[i], it->n);
            chk(d[i], it->n);
            S.erase(S.begin());
        }
        int tmp = root(d[i]);
        if(e[tmp] == tmp)
        {
            printf("IMPOSSIBLE");
            return 0;
        }
        if(end!=-1)
            S.insert(R(s, end, e[tmp]));
        S.insert(R(t, t, d[i]));
    }
//  for(i=1; i<=n; i++) printf("%d %d\n", p[i], e[i]);
    t = root(1);
    for(i=1; i<=2*n; i++)
    {
        if(root(d[i]) == t) printf("^");
        else
        {
            printf("v");
            chk(d[i], t);
            t = root(t);
        }
    }
    return 0;
}

Subtask #1
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 8240 KB Output is correct
2 Correct 0 ms 8240 KB Output is correct
3 Correct 0 ms 8240 KB Output is correct
4 Correct 0 ms 8240 KB Output is correct
5 Correct 0 ms 8240 KB Output is correct
6 Correct 0 ms 8240 KB Output is correct
7 Correct 0 ms 8240 KB Output is correct
8 Correct 0 ms 8240 KB Output is correct
9 Correct 0 ms 8240 KB Output is correct
10 Correct 0 ms 8240 KB Output is correct
11 Correct 0 ms 8240 KB Output is correct
12 Correct 0 ms 8240 KB Output is correct
13 Correct 0 ms 8240 KB Output is correct
14 Correct 0 ms 8240 KB Output is correct
15 Incorrect 0 ms 8240 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #2
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Halted 0 ms 0 KB -

Subtask #3
0.0 / 37.0

# Verdict Execution time Memory Grader output
1 Halted 0 ms 0 KB -

Subtask #4
0.0 / 39.0

# Verdict Execution time Memory Grader output
1 Halted 0 ms 0 KB -