Submission #18425

#	Time	Username	Problem	Language	Result	Execution time	Memory
18425		tlwpdus	전선 연결하기 (GA9_wire)	C++98	0 / 100	16 ms	43408 KiB

wire

#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 / 9
• Subtask 2: 0 / 15
• Subtask 3: 0 / 37
• Subtask 4: 0 / 39