SCPC 2021 Round1 후기

작성일 | In |

결과 및 총평


어제 오후 3시에 거의 바로 시작했고, 저녁 먹기 전에 끝내려고 했다. 약간 설렁설렁했는데, 어쨌든 6시 전에 올솔브에, 전부 한번에 맞았다. 그래서 기분 좋게 저녁 먹으러 갔었다.

종료 후 전체 솔브 수는 차레로 1305/661/315/232/147였다.

솔브 수에서 보이듯 예년 보다 전체적으로 난이도가 쉬웠다. 작년 Round2 제출자가 500명을 살짝 넘은 것으로 보이는데, 올해는 1,2번 모두 만점 받은 사람이 500을 훨씬 넘긴 것을 보면, 어떻게 될진 모르겠지만 3번까지 긁기는 해야 안심할 수 있지 않을까 싶다.

아래는 각 문제의 간단한 풀이와 코드이다. 문제 지문은 나중에 codeground의 practice에 올라올 테니, 여기선 독자가 문제를 읽었다고 가정한다.

1. 친구들

각 사람을 정점으로 생각하고, 친구 관계를 간선으로 이어진 것이라 생각하면 결국 이 graph에서, connected component는 완전 그래프(perfect graph)가 된다. 따라서 연결 컴포넌트 개수가 곧 정답이 된다. 이는 union-find나 dfs로 쉽게 구현 가능하다. 나의 경우 dfs를 사용해 컴포넌트 수를 세었다. connected component만 판단하면 되니, 봐야 하는 간선은 각 $i$에 대해 $i$와 $i+D_{i}$를 있는 간선 밖에 없다.

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include <bits/stdc++.h>
#define f first
#define s second
#define MOD 1000000007
#define PMOD 998244353
#define pb(x) push_back(x)
using namespace std;

typedef long long int ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> plii;
typedef pair<int, pii> piii;
const int INF = 1e9+10;
const ll LINF = 1LL*INF*INF;
const int MAXN = 2e5+10;
const int MAXM = 5e3+10;

priority_queue<int> pq;
vector<vector<int> > graph;
queue<int> que;

int A[MAXN];
bool vis[MAXN];
char S[MAXN];

void dfs(int here)
{
    vis[here] = true;

    int there;

    for(int i=0;i<(int)graph[here].size();i++){
        there = graph[here][i];
        if(vis[there])continue;
        dfs(there);
    }

    return;
}

int main()
{
    int n,m,k,a,b,x,y,q;
    int sum = 0;
    int cnt = 0;
    int mx = 0;
    int mn = INF;
    int cur = 0, idx = -1;
    int tc;

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin>>tc;

    for(int runs=1;runs<=tc;runs++){

        cin>>n;

        for(int i=1;i<=n;i++){
            cin>>A[i];
        }

        graph = vector<vector<int> > (n+1);

        for(int i=1;i<=n;i++){
            cur = i+A[i];
            if(cur>n)continue;
            graph[i].push_back(cur);
            graph[cur].push_back(i);
        }

        fill(vis,vis+n+1,false);

        cnt = 0;

        for(int i=1;i<=n;i++){
            if(vis[i])continue;
            cnt++;
            dfs(i);
        }

        cout<<"Case #"<<runs<<"\n";
        cout<<cnt<<"\n";
    }


    return 0;
}

2. 이진수

살짝 귀찮았던 문제, 결국 각 $b_{i}$는 $a_{i-t} or a_{i+t}$로 정해진다는 것을 알 수 있다. 그러므로 역추적을 위해서 다음과 같이 하면 된다.

  • $b_{i} = 0$인 경우, $a_{i-t},a_{i+t}$ 모두 (존재한다면) 0으로 정한다.
  • $b_{i} = 1$이고, $a_{i-t},a_{i+t}$ 중 한 쪽이 없거나, 한 쪽이 0으로 정해진 경우, 다른쪽엔 1로 값을 정한다.
  • $a_{i}$ 중 아직 정해지지 않은 값들에 대해서, greedy하게 앞에서 부터 순서대로 보면서, 아무렇게 해도 상관없다면 (그런 문자열이 존재한다면) 0으로, 반드시 1로 해야 한다면 1로 정해준다.

자세한 부분은 구현을 참고.

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include <bits/stdc++.h>
#define f first
#define s second
#define MOD 1000000007
#define PMOD 998244353
#define pb(x) push_back(x)
using namespace std;

typedef long long int ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> plii;
typedef pair<int, pii> piii;
const int INF = 1e9+10;
const ll LINF = 1LL*INF*INF;
const int MAXN = 2e5+10;
const int MAXM = 5e3+10;

priority_queue<int> pq;
vector<vector<int> > graph;
queue<int> que;

int A[MAXN];
char S[MAXN];
char T[MAXN];

int main()
{
    int n,m,k,a,b,x,y,q;
    int sum = 0;
    int cnt = 0;
    int mx = 0;
    int mn = INF;
    int cur = 0, idx = -1;
    int tc;

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin>>tc;

    for(int runs=1;runs<=tc;runs++){

        cin>>n>>k;
        cin>>S+1;

        fill(A,A+n+1,-1);

        for(int i=1;i<=n;i++){
            if(S[i]=='0'){
                if(i>k)A[i-k] = 0;
                if(i+k<=n)A[i+k] = 0;
            }
        }

        bool judge = true;

        for(int i=1;i<=n;i++){
            if(S[i]=='1'){
                if(i>k&&i+k<=n){
                    if(A[i-k]==0)A[i+k] = 1;
                    else if(A[i+k]==0)A[i-k] = 1;
                }
                else if(i>k){
                    A[i-k] = 1;
                }
                else if(i+k<=n){
                    A[i+k] = 1;
                }
            }
        }

        for(int i=1;i<=min((k<<1),n);i++){
            if(A[i]==-1)A[i] = 0;
        }

        for(int i=k+1;i<=n;i++){
            if(S[i]=='1'){
                if(i+k<=n&&A[i+k]==-1){
                    A[i+k] = 1^A[i-k];
                }
            }
        }

        for(int i=1;i<=n;i++){
            if(A[i]==-1)T[i] = '0';
            else T[i] = A[i]+'0';
        }
        T[n+1] = 0;

        cout<<"Case #"<<runs<<"\n";
        cout<<T+1<<"\n";
    }

    return 0;
}

3. No Cycle

그냥 가능한 정답을 묻는다면, 전체를 위상 정렬 시킨 후, 각 정점의 위상정렬상에서의 순서만 따져서 정답을 작성해도 된다. 하지만 이 문제에선 사전순으로 최소라는 조건이 붙으므로, 위와 같은 방식은 WA를 낸다. 다시 제한을 보면 $N \leq 500$, $M, K \leq 2000$으로 그렇게 크지 않다는 것을 알 수 있다. 그러니 각 간선의 방향을 결정할 때 마다 간선을 추가시켜 주면서, 지금 현재 정방향(결과에서 0으로 나타나는 방향)으로 추가가 가능한지 보고, 가능하면 정방향으로, 그렇지 않다면 역방향으로 간선 방향을 정해주면 된다. 이때 가능한지 판단은 dfs를 통해 했다.

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include <bits/stdc++.h>
#define f first
#define s second
#define MOD 1000000007
#define PMOD 998244353
#define pb(x) push_back(x)
using namespace std;

typedef long long int ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> plii;
typedef pair<int, pii> piii;
const int INF = 1e9+10;
const ll LINF = 1LL*INF*INF;
const int MAXN = 2e5+10;
const int MAXM = 5e3+10;

priority_queue<int> pq;
vector<vector<int> > graph;
queue<int> que;

int A[MAXN];

bool vis[MAXN];
pii edge[MAXN];
char S[MAXN];

void dfs(int here){

    int there;

    vis[here] = true;

    for(int i=0;i<graph[here].size();i++){
        there = graph[here][i];
        if(!vis[there])dfs(there);
    }

    return;
}

int main()
{
    int n,m,k,a,b,x,y,q;
    int sum = 0;
    int cnt = 0;
    int mx = 0;
    int mn = INF;
    int cur = 0, idx = -1;
    int tc;

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin>>tc;

    for(int runs=1;runs<=tc;runs++){

        cin>>n>>m>>k;

        graph = vector<vector<int> > (n+1);

        for(int i=0;i<m;i++){
            cin>>x>>y;
            graph[x].push_back(y);
        }

        for(int i=0;i<k;i++){
            cin>>edge[i].f>>edge[i].s;
        }

        for(int i=0;i<k;i++){

            fill(vis,vis+n+1,false);

            a = edge[i].f;
            b = edge[i].s;

            dfs(b);

            if(vis[a]){
                S[i] = '1';
            }
            else {
                S[i] = '0';
                graph[a].push_back(b);
            }
        }
        S[k] = 0;

        cout<<"Case #"<<runs<<"\n";
        cout<<S<<"\n";
    }


    return 0;
}

4. 예약 시스템

이 문제의 핵심은 $p(c) = w_{a}+w_{b}$이므로, 그룹 마다 스트레스를 따로 따로 생각할 수 있단 점이다. 결국 총 페널티는 각 그룹에 대해, 그룹에서 다른 그룹과 이웃한 개수가 몇 개인지에 따라 달려 있다. 간단히 생각해 보면 같은 그룹 끼리 뭉쳐 있을 수록 페널티가 작아질 것이라 생각할 수 있다. (문제를 풀 당시엔 이렇게 생각했는데, 반례가 존재한다고 한다. 그리고 문제도 수정됐다…) 짝수개일 때는 직사각형 모양, 홀수일 경우 직사각형에서 정사각형 하나가 붙어 있는 모양이다. 이때 그룹의 인원 수가 작으면 계산이 달라질 수 있지만, 다행히 각 그룹 인원 수가 5이상이기 때문에, 달라지지 않는다.

이제 남은 것은 적절한 case-work이다. 양 끝에 있는 그룹의 인원수가 홀수/홀수 인 경우, 짝수/짝수 인 경우, 홀수/짝수 인 경우로, 나누어, 각각의 최솟값을 구해서 전체 최솟값을 구하면 된다. 제한에서 홀수인 그룹의 개수는 짝수가 될수 밖에 없음에 유의하라.

자세한 부분은 역시 코드를 참고.

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
#include <bits/stdc++.h>
#define f first
#define s second
#define MOD 1000000007
#define PMOD 998244353
#define pb(x) push_back(x)
using namespace std;

typedef long long int ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> plii;
typedef pair<int, pii> piii;
const int INF = 1e9+10;
const ll LINF = 1LL*INF*INF;
const int MAXN = 2e5+10;
const int MAXM = 5e3+10;

priority_queue<int> pq;
vector<vector<int> > graph;
queue<int> que;

int A[MAXN];
char S[MAXN];

vector<int> val[MAXN];

ll getbotheven(int n){

    int evencnt = 0;

    for(int i=1;i<=n;i++){

        if(!(A[i]&1))evencnt++;

    }

    if(evencnt<2)return LINF;

    ll mx = 0;
    ll mx2 = 0;
    ll curmx = 0;
    ll curv = 0;
    ll tot = 0;

    for(int i=1;i<=n;i++){

        if(A[i]&1){
            curv = (val[i][0]<<1)+val[i][1]+val[i][2]+val[i][3];
            curmx = 0;
        }
        else {
            curv = val[i][0]+val[i][1]+val[i][2]+val[i][3];
            curmx = val[i][2]+val[i][3];
        }
        tot += curv;
        if(mx<curmx){
            mx2 = mx;
            mx = curmx;
        }
        else {
            mx2 = max(mx2,curmx);
        }
    }

    tot-=(mx+mx2);

    return tot;
}

ll getbothodd(int n){

    int oddcnt = 0;

    for(int i=1;i<=n;i++){
        if(A[i]&1)oddcnt++;
    }

    if(!oddcnt)return LINF;

    ll curv = 0;
    ll tot = 0;
    ll mx = 0;
    ll mx2 = 0;
    ll curmx = 0;

    if(oddcnt==2){

        for(int i=1;i<=n;i++){

            if(A[i]&1){
                curv = (val[i][0]<<1)+val[i][1];
            }
            else {
                curv = (val[i][0]<<1)+(val[i][1]<<1)+val[i][2]+val[i][3];
            }
            tot += curv;
        }
    }
    else {

        for(int i=1;i<=n;i++){

            if(A[i]&1){
                curv = (val[i][0]<<1)+val[i][1]+val[i][2]+val[i][3];
                curmx = val[i][2]+val[i][3];
            }
            else {
                curv = val[i][0]+val[i][1]+val[i][2]+val[i][3];
                curmx = 0;
            }

            tot += curv;
            if(mx<curmx){
                mx2 = mx;
                mx = curmx;
            }
            else {
                mx2 = max(mx2,curmx);
            }
        }

        tot-=(mx+mx2);
    }

    return tot;
}

ll getdiff(int n){

    int oddcnt = 0;

    for(int i=1;i<=n;i++){
        if(A[i]&1)oddcnt++;
    }

    if(!oddcnt)return LINF;
    if(oddcnt==n)return LINF;

    ll oddmx = 0;
    ll evenmx = 0;
    ll curmx = 0;
    ll curv = 0;
    ll tot = 0;

    for(int i=1;i<=n;i++){

        if(A[i]&1){
            curv = (val[i][0]<<1)+val[i][1]+val[i][2]+val[i][3];
            curmx = val[i][2]+val[i][3];
            oddmx = max(oddmx,curmx);
        }
        else {
            curv = val[i][0]+val[i][1]+val[i][2]+val[i][3];
            curmx = val[i][2]+val[i][3];
            evenmx = max(evenmx,curmx);
        }
        tot += curv;
    }

    tot-=(oddmx+evenmx);
    return tot;
}

int main()
{
    int n,m,k,a,b,x,y,q;
    int sum = 0;
    int cnt = 0;
    int mx = 0;
    int mn = INF;
    int cur = 0, idx = -1;
    int tc;

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin>>tc;

    for(int runs=1;runs<=tc;runs++){

        cin>>n>>m;

        for(int i=1;i<=n;i++){

            cin>>k;

            val[i].clear();
            A[i] = k;

            for(int j=0;j<k;j++){
                cin>>x;
                val[i].push_back(x);
            }

            sort(val[i].begin(),val[i].end());
        }

        ll res = LINF;

        if(n==1){
            res = 0;
        }
        else {
            res = min(res,getbotheven(n));
            res = min(res,getbothodd(n));
            res = min(res,getdiff(n));
        }

        cout<<"Case #"<<runs<<"\n";

        cout<<res<<"\n";
    }

    return 0;
}

5. 차이

가장 어려운 문제이면서도, 가장 전형적인 문제 였다고 생각한다.

문제의 어투(?)에서 느낄 수 있듯이 1번 쿼리에서, 정점 $i$와 $j$를 간선으로 있는 것처럼 생각할 수 있다. 물론 방향에 따라 가중치의 부호는 달라진다.

이제 2번 쿼리에서, NC인지 아닌지 부터 판단해보자. 어떤 정점 $i$와 $j$가 하나의 connected component 안에 있다면, 문제에서 주어진 것처럼 경로를 구성할 수 있음을 알 수 있다. 따라서, 하나의 connected component안에 있다면, NC가 아니고, 그렇지 않다면 NC 이다.

다시 1번 쿼리로 돌아가서, $i$와 $j$를 이으려 하는 상황을 보자. $i$와 $j$가 다른 connected component 안에 있으면 그냥 이어주면 된다. 같은 connected component라면 이제, $X_{i}-X_{j}$를 알아낼 수 있으므로, 업데이트 하려는 정보와 구한 정보를 비교한다. 만약에 같다면, 앞으로도 유일하게 결정 가능하므로 넘어간다. 하지만 다르다면, 지금 component내의 임의의 정점 $a,b$에 대해 $X_{a}-X_{b}$가 유일하게 결정되지 않는다. 따라서, 이 component에서 유일하게 결정할 수 없다고 표시해주어야 한다. 이후 2번 쿼리가 들어왔을 때, 같은 component 안에 있기는 하나 그 component에 이 표시가 되어 있다면 CF를 출력하면 된다.

이제 NC,CF 도 아닌 경우에 어떻게 구하는지 본다. 먼저 1번 쿼리에서 $i$와 $j$를 이을 때, 같은 component라면 간선을 추가할 필요가 없다는 것을 쉽게 알 수 있다. 따라서, graph의 형태는 forest가 된다. 쿼리들을 online으로 처리하는 것이 강제된다면 link-cut tree 같은 어려운 자료구조를 써야하지만, 지금같이 모든 정보가 주어지는 경우에는 그럴 필요가 없다. 최종 forest의 형태가 주어져 있으므로, 그에 따라 구성하면 된다.

구현하는 방법에는 여러 가지가 있겠지만, 나의 경우 전체 forest를 0번 정점을 추가해서 하나의 tree로 만든 후, dfs ordering + indextree를 사용해서 구했다. 그 외에 NC, CF 등의 판단은 union-find를 사용했다. union-find에서 union을 할 때 conflict 정보를 넘겨주어야 함에 유의하라.

자세한 구현은 코드 참고.

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
#include <bits/stdc++.h>
#define f first
#define s second
#define MOD 1000000007
#define PMOD 998244353
#define pb(x) push_back(x)
using namespace std;

typedef long long int ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> plii;
typedef pair<int, pii> piii;
const int INF = 1e9+10;
const ll LINF = 1LL*INF*INF;
const int MAXN = 2e5+10;
const int MAXM = 5e3+10;

priority_queue<int> pq;
vector<vector<int> > graph;
queue<int> que;

pii query[MAXN];
ll val[MAXN];
int ty[MAXN];

int par[MAXN];

int pp[MAXN];
int in[MAXN];
int out[MAXN];

bool iscon[MAXN];

ll tree[MAXN*4];

int root(int x){
    if(par[x]==x)return x;
    else return par[x] = root(par[x]);
}

int seq;

void dfs(int here,int p){

    int there;

    in[here] = seq;
    seq++;

    for(int i=0;i<graph[here].size();i++){
        there = graph[here][i];
        if(there==p)continue;
        pp[there] = here;
        dfs(there,here);
    }

    out[here] = seq-1;

    return;
}

inline void update(int L,int R,ll v){

    while(L<=R){

        if(L&1){
            tree[L]+=v;
            L++;
        }
        if(!(R&1)){
            tree[R]+=v;
            R--;
        }
        L>>=1; R>>=1;
    }

    return;
}

inline ll getans(int tmp){

    ll res = 0;

    while(tmp){
        res += tree[tmp];
        tmp>>=1;
    }

    return res;
}

inline ll getdis(int base,int a,int b){

    ll ansa = getans(base+in[a]);
    ll ansb = getans(base+in[b]);

    return ansa-ansb;
}

void solve(int n,int m){

    int a,b;
    int x,y;

    graph = vector<vector<int> > (n+1);

    for(int i=1;i<=n;i++){
        par[i] = i;
    }

    for(int i=0;i<m;i++){
        if(ty[i]==2)continue;

        x = query[i].f;
        y = query[i].s;

        a = root(x);
        b = root(y);

        if(a^b){
            par[b] = a;
            graph[x].push_back(y);
            graph[y].push_back(x);
        }

    }

    for(int i=1;i<=n;i++){
        if(par[i]==i){
            graph[0].push_back(i);
            graph[i].push_back(0);
        }
    }

    seq = 0;

    dfs(0,-1);
    pp[0] = -1;

    int base = 1;

    for(;base<=n;base<<=1);

    fill(tree,tree+(base<<1),0);

    fill(iscon,iscon+n+1,false);

    for(int i=1;i<=n;i++){
        par[i] = i;
    }

    ll curd = 0;

    for(int i=0;i<m;i++){

        x = query[i].f;
        y = query[i].s;

        a = root(x);
        b = root(y);

        if(ty[i]==1){

            if(a^b){
                par[b] = a;
                iscon[a] |= iscon[b];

                if(pp[x]==y)update(base+in[x],base+out[x],val[i]);
                else update(base+in[y],base+out[y],-val[i]);
            }
            else {

                curd = getdis(base,x,y);

                if(curd!=val[i])iscon[a] = true;
            }
        }
        else {

            if(a^b){
                cout<<"NC\n";
            }
            else {
                if(iscon[a])cout<<"CF\n";
                else {
                    curd = getdis(base,x,y);
                    cout<<curd<<"\n";
                }
            }
        }
    }

    return;
}

int main()
{
    int n,m,k,a,b,x,y,q;
    int sum = 0;
    int cnt = 0;
    int mx = 0;
    int mn = INF;
    int cur = 0, idx = -1;
    int tc;

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin>>tc;

    for(int runs=1;runs<=tc;runs++){

        cin>>n>>m;

        for(int i=0;i<m;i++){
            cin>>ty[i];
            if(ty[i]&1){
                cin>>query[i].f>>query[i].s>>val[i];
            }
            else {
                cin>>query[i].f>>query[i].s;
            }
        }

        cout<<"Case #"<<runs<<"\n";

        solve(n,m);
    }

    return 0;
}