Submission #12130

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
12130	2014-12-21 07:50:36	kriii	전선 연결하기 (GA9_wire)	C++14	24 / 100	1000 ms	5344 KiB

wire

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <stdio.h>
#include <queue>
int n,s[300001],e[300001],c[300001];
char ans[600002];
int main()
{
  scanf ("%d",&n);
  for (int i=1;i<=2*n;i++){
    int x; scanf ("%d",&x);
    if (!s[x]) s[x] = i;
    else e[x] = i;
  }
  for (int i=1;i<=n;i++) c[i] = -1;
  
  for (int i=1;i<=n;i++) if (c[i] == -1){
    std::queue<int> Q; Q.push(i);
    c[i] = 0;
    while (!Q.empty()){
      int x = Q.front(); Q.pop();
      for (int j=1;j<=n;j++) if (j != x){
        bool a = s[x] < s[j] && s[j] < e[x];
        bool b = s[x] < e[j] && e[j] < e[x];
        if (a ^ b){
          if (c[j] != -1){
            if (c[j] == c[x]){
              puts("IMPOSSIBLE");
              return 0;
            }
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• Subtask 1: 9 / 9
• Subtask 2: 15 / 15
• Subtask 3: 0 / 37
• Subtask 4: 0 / 39