oj.uz

Submission #18425

# Submission time Handle Problem Language Result Execution time Memory
18425 2016-02-01T10:56:02 Z tlwpdus 전선 연결하기 (GA9_wire) C++
0 / 100
 16 ms 43408 KB 
#include<stdio.h>
#include<algorithm>
#include<set>
#include<vector>
#include<string.h>

#define MAXN 100010

using namespace std;

vector<int> lis[MAXN];

struct unionfind {
    int par[MAXN];
    void init(int n) {
        int i;
        for (i=0;i<n;i++) par[i] = i;
    }
    int find(int u) {
        if (u==par[u]) return u;
        return (par[u] = find(par[u]));
    }
    bool uni(int u, int v) {
        u = find(u), v = find(v);
        if (u==v) return false;
        par[u] = v;
        return true;
    }
} unf;

struct segtree {
    set<int> tree[8*MAXN];
    int key;
    void init(int n) {
        key = 1;
        while(key<n) key*=2;
    }
    void update(int idx, int val, int type) {
        idx+=key;
        while(idx>0) {
            if (type==1) tree[idx].insert(val);
            else tree[idx].erase(val);
            idx/=2;
        }
    }
    bool put(int idx, int v) {
        set<int>::iterator it = tree[idx].begin();
        for (;it!=tree[idx].end();it++) {
            if (!unf.uni(*it,v)) return false;
            lis[v].push_back(*it);
            lis[*it].push_back(v);
        }
        return true;
    }
    bool query(int s, int e, int v) {
        s+=key;
        e+=key;
        while(s<=e) {
            if (s%2==1) if (!put(s++,v)) return false;
            if (e%2==0) if (!put(e--,v)) return false;
            s >>= 1;
            e >>= 1;
        }
        return true;
    }
} seg;

int n;
int arr[2*MAXN];
int loc[MAXN][2];
int ud[MAXN];

void dfs(int here, int p, int st) {
    ud[here] = st;
    int i;
    for (i=0;i<lis[here].size();i++) {
        int there = lis[here][i];
        if (there==p) continue;
        dfs(there,here,-st);
    }
}

void finish() {
    printf("IMPOSSIBLE\n");
    return;
}
void process() {
    int i;
    unf.init(n+2);
    seg.init(2*n+2);
    for (i=0;i<2*n;i++) {
        if (loc[arr[i]][0]==i) {
            if (!seg.query(loc[arr[i]][0]+1,loc[arr[i]][1]-1,arr[i])) {
                finish();return;
            }
            seg.update(loc[arr[i]][1],arr[i],1);
        }
        else seg.update(loc[arr[i]][1],arr[i],0);
    }
    for (i=0;i<n;i++) if (ud[i]==0) dfs(i,-1,1);
    for (i=0;i<2*n;i++) {
        if (ud[arr[i]]==1) printf("^");
        else printf("v");
    }
    printf("\n");
}

void input() {
    int i;
    scanf("%d",&n);
    memset(loc,-1,sizeof(loc));
    for (i=0;i<2*n;i++) {
        scanf("%d",&arr[i]);
        arr[i]--;
        if (loc[arr[i]][0]==-1) loc[arr[i]][0] = i;
        else loc[arr[i]][1] = i;
    }
}

int main() {
    input();
    process();
    return 0;
}

Subtask #1
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 43408 KB Output is correct
2 Correct 5 ms 43408 KB Output is correct
3 Correct 12 ms 43408 KB Output is correct
4 Correct 5 ms 43408 KB Output is correct
5 Correct 8 ms 43408 KB Output is correct
6 Correct 12 ms 43408 KB Output is correct
7 Correct 13 ms 43408 KB Output is correct
8 Correct 12 ms 43408 KB Output is correct
9 Correct 13 ms 43408 KB Output is correct
10 Correct 16 ms 43408 KB Output is correct
11 Correct 13 ms 43408 KB Output is correct
12 Correct 12 ms 43408 KB Output is correct
13 Correct 4 ms 43408 KB Output is correct
14 Correct 5 ms 43408 KB Output is correct
15 Correct 16 ms 43408 KB Output is correct
16 Correct 12 ms 43408 KB Output is correct
17 Correct 11 ms 43408 KB Output is correct
18 Correct 6 ms 43408 KB Output is correct
19 Correct 12 ms 43408 KB Output is correct
20 Correct 4 ms 43408 KB Output is correct
21 Incorrect 12 ms 43408 KB Output isn't correct
22 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 -