시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 871 223 142 24.357%

문제

종빈이는 아주 큰 그룹의 총수다. 이 그룹은 1부터 N번까지의 번호로 구분할 수 있는 N개의 기업을 운영하고 있다. 현재 각 기업은 서로 독립적인 자체 컴퓨팅 및 통신센터를 가지고 있다.

어느 날 종빈이는 계열사의 CTO인 서현이에게 서비스 개선을 위해 각 기업의 서버를 네트워크로 연결하여 단일 통신센터에서 관리 가능한 클러스터 형태로 구성할 것을 제안했다. 종빈이의 제안을 들은 서현이는 다음과 같은 병합 과정을 고안해냈다.

  1. 클러스터 A를 제공하는 기존에 존재하는 센터 I를 고른다.
  2. 클러스터 B를 제공하는 기업 J를 고른다. B는 A가 아닌 임의의 클러스터이며, J는 센터가 아닐 수 있다.
  3. I와 J를 통신 라인으로 연결한다. 이때 기업 I와 J를 잇는 라인의 길이는 |I – J|(mod 1000)이다.
  4. 위 방식을 통해 클러스터 A와 B는 새로운 클러스터로 합쳐지며, 이 클러스터는 B의 센터에 의해 제공된다.

이러한 병합 과정을 거치던 중에, 각 기업에서 현재 센터까지 연결되는 라인의 길이가 총 얼마나 되는지에 관한 문의가 들어왔다. 서현이를 위해 병합하는 과정과 그 과정에서 통신센터와 각 기업을 잇는 라인의 길이를 구하는 프로그램을 작성해보자.

입력

입력은 여러 개의 테스트케이스로 주어진다. 입력의 첫 번째 줄에는 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스에는 기업의 수를 나타내는 N(4 ≤ N ≤ 20,000)이 주어진다. 다음은 몇 개의 줄에 걸쳐 아래 두 가지 종류의 명령어가 들어온다.

  • E I – 기업 I와 현재 I의 센터까지의 거리를 출력한다. 
  • I I J – 센터 I를 기업 J에 연결한다.

각 테스트케이스의 끝에는 단어 O가 주어진다. 각 테스트케이스에서 명령어의 총 개수는 200,000개를 넘지 않으며, 그중 I 명령어의 개수는 N개보다 작다.

출력

E 명령어가 들어올 때마다 한 줄에 해당 거리를 출력한다.

예제 입력 1

1
4
E 3
I 3 1
E 3
I 1 2
E 3
I 2 4
E 3
O

예제 출력 1

0
2
3
5
W3sicHJvYmxlbV9pZCI6IjM3ODAiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWIxMjRcdWQyYjhcdWM2Y2NcdWQwNmMgXHVjNWYwXHVhY2IwIiwiZGVzY3JpcHRpb24iOiI8cD5cdWM4ODVcdWJlNDhcdWM3NzRcdWIyOTQgXHVjNTQ0XHVjOGZjIFx1ZDA3MCBcdWFkZjhcdWI4ZjlcdWM3NTggXHVjZDFkXHVjMjE4XHViMmU0LiBcdWM3NzQgXHVhZGY4XHViOGY5XHVjNzQwIDFcdWJkODBcdWQxMzAgTlx1YmM4OFx1YWU0Y1x1YzljMFx1Yzc1OCBcdWJjODhcdWQ2MzhcdWI4NWMgXHVhZDZjXHViZDg0XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyOTQgTlx1YWMxY1x1Yzc1OCBcdWFlMzBcdWM1YzVcdWM3NDQgXHVjNmI0XHVjNjAxXHVkNTU4XHVhY2UwIFx1Yzc4OFx1YjJlNC4gXHVkNjA0XHVjN2FjIFx1YWMwMSBcdWFlMzBcdWM1YzVcdWM3NDAgXHVjMTFjXHViODVjIFx1YjNjNVx1YjliZFx1YzgwMVx1Yzc3OCBcdWM3OTBcdWNjYjQgXHVjZWY0XHVkNGU4XHVkMzA1IFx1YmMwZiBcdWQxYjVcdWMyZTBcdWMxM2NcdWQxMzBcdWI5N2MgXHVhYzAwXHVjOWMwXHVhY2UwIFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNWI0XHViMjkwIFx1YjBhMCBcdWM4ODVcdWJlNDhcdWM3NzRcdWIyOTQgXHVhY2M0XHVjNWY0XHVjMGFjXHVjNzU4IENUT1x1Yzc3OCBcdWMxMWNcdWQ2MDRcdWM3NzRcdWM1ZDBcdWFjOGMgXHVjMTFjXHViZTQ0XHVjMmE0IFx1YWMxY1x1YzEyMFx1Yzc0NCBcdWM3MDRcdWQ1NzQgXHVhYzAxIFx1YWUzMFx1YzVjNVx1Yzc1OCBcdWMxMWNcdWJjODRcdWI5N2MgXHViMTI0XHVkMmI4XHVjNmNjXHVkMDZjXHViODVjIFx1YzVmMFx1YWNiMFx1ZDU1OFx1YzVlYyBcdWIyZThcdWM3N2MgXHVkMWI1XHVjMmUwXHVjMTNjXHVkMTMwXHVjNWQwXHVjMTFjIFx1YWQwMFx1YjlhYyBcdWFjMDBcdWIyYTVcdWQ1NWMgXHVkMDc0XHViN2VjXHVjMmE0XHVkMTMwIFx1ZDYxNVx1ZDBkY1x1Yjg1YyBcdWFkNmNcdWMxMzFcdWQ1NjAgXHVhYzgzXHVjNzQ0IFx1YzgxY1x1YzU0OFx1ZDU4OFx1YjJlNC4gXHVjODg1XHViZTQ4XHVjNzc0XHVjNzU4IFx1YzgxY1x1YzU0OFx1Yzc0NCBcdWI0ZTRcdWM3NDAgXHVjMTFjXHVkNjA0XHVjNzc0XHViMjk0IFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NDAgXHViY2QxXHVkNTY5IFx1YWNmY1x1YzgxNVx1Yzc0NCBcdWFjZTBcdWM1NDhcdWQ1NzRcdWIwYzhcdWIyZTQuPFwvcD5cclxuXHJcbjxvbD5cclxuXHQ8bGk+XHVkMDc0XHViN2VjXHVjMmE0XHVkMTMwIEFcdWI5N2MgXHVjODFjXHVhY2Y1XHVkNTU4XHViMjk0IFx1YWUzMFx1Yzg3NFx1YzVkMCBcdWM4NzRcdWM3YWNcdWQ1NThcdWIyOTQgXHVjMTNjXHVkMTMwIElcdWI5N2MgXHVhY2UwXHViOTc4XHViMmU0LjxcL2xpPlxyXG5cdDxsaT5cdWQwNzRcdWI3ZWNcdWMyYTRcdWQxMzAgQlx1Yjk3YyBcdWM4MWNcdWFjZjVcdWQ1NThcdWIyOTQgXHVhZTMwXHVjNWM1IEpcdWI5N2MgXHVhY2UwXHViOTc4XHViMmU0LiBCXHViMjk0IEFcdWFjMDAgXHVjNTQ0XHViMmNjIFx1Yzc4NFx1Yzc1OFx1Yzc1OCBcdWQwNzRcdWI3ZWNcdWMyYTRcdWQxMzBcdWM3NzRcdWJhNzAsIEpcdWIyOTQgXHVjMTNjXHVkMTMwXHVhYzAwIFx1YzU0NFx1YjJkMCBcdWMyMTggXHVjNzg4XHViMmU0LjxcL2xpPlxyXG5cdDxsaT5JXHVjNjQwIEpcdWI5N2MgXHVkMWI1XHVjMmUwIFx1Yjc3Y1x1Yzc3OFx1YzczY1x1Yjg1YyBcdWM1ZjBcdWFjYjBcdWQ1NWNcdWIyZTQuIFx1Yzc3NFx1YjU0YyBcdWFlMzBcdWM1YzUgSVx1YzY0MCBKXHViOTdjIFx1Yzc4N1x1YjI5NCBcdWI3N2NcdWM3NzhcdWM3NTggXHVhZTM4XHVjNzc0XHViMjk0IHxJICZuZGFzaDsgSnwobW9kIDEwMDApXHVjNzc0XHViMmU0LjxcL2xpPlxyXG5cdDxsaT5cdWM3MDQgXHViYzI5XHVjMmRkXHVjNzQ0IFx1ZDFiNVx1ZDU3NCBcdWQwNzRcdWI3ZWNcdWMyYTRcdWQxMzAgQVx1YzY0MCBCXHViMjk0IFx1YzBjOFx1Yjg1Y1x1YzZiNCBcdWQwNzRcdWI3ZWNcdWMyYTRcdWQxMzBcdWI4NWMgXHVkNTY5XHVjY2QwXHVjOWMwXHViYTcwLCBcdWM3NzQgXHVkMDc0XHViN2VjXHVjMmE0XHVkMTMwXHViMjk0IEJcdWM3NTggXHVjMTNjXHVkMTMwXHVjNWQwIFx1Yzc1OFx1ZDU3NCBcdWM4MWNcdWFjZjVcdWI0MWNcdWIyZTQuPFwvbGk+XHJcbjxcL29sPlxyXG5cclxuPHA+XHVjNzc0XHViN2VjXHVkNTVjIFx1YmNkMVx1ZDU2OSBcdWFjZmNcdWM4MTVcdWM3NDQgXHVhYzcwXHVjZTU4XHViMzU4IFx1YzkxMVx1YzVkMCwgXHVhYzAxIFx1YWUzMFx1YzVjNVx1YzVkMFx1YzExYyBcdWQ2MDRcdWM3YWMgXHVjMTNjXHVkMTMwXHVhZTRjXHVjOWMwIFx1YzVmMFx1YWNiMFx1YjQxOFx1YjI5NCBcdWI3N2NcdWM3NzhcdWM3NTggXHVhZTM4XHVjNzc0XHVhYzAwIFx1Y2QxZCBcdWM1YmNcdWI5YzhcdWIwOTggXHViNDE4XHViMjk0XHVjOWMwXHVjNWQwIFx1YWQwMFx1ZDU1YyBcdWJiMzhcdWM3NThcdWFjMDAgXHViNGU0XHVjNWI0XHVjNjU0XHViMmU0LiBcdWMxMWNcdWQ2MDRcdWM3NzRcdWI5N2MgXHVjNzA0XHVkNTc0IFx1YmNkMVx1ZDU2OVx1ZDU1OFx1YjI5NCBcdWFjZmNcdWM4MTVcdWFjZmMgXHVhZGY4IFx1YWNmY1x1YzgxNVx1YzVkMFx1YzExYyBcdWQxYjVcdWMyZTBcdWMxM2NcdWQxMzBcdWM2NDAgXHVhYzAxIFx1YWUzMFx1YzVjNVx1Yzc0NCBcdWM3ODdcdWIyOTQgXHViNzdjXHVjNzc4XHVjNzU4IFx1YWUzOFx1Yzc3NFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU3NFx1YmNmNFx1Yzc5MC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Yzc4NVx1YjgyNVx1Yzc0MCBcdWM1ZWNcdWI3ZWMgXHVhYzFjXHVjNzU4IFx1ZDE0Y1x1YzJhNFx1ZDJiOFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1Yzc4NVx1YjgyNVx1Yzc1OCBcdWNjYWIgXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YWMxY1x1YzIxOCBUXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDBcdWIyOTQgXHVhZTMwXHVjNWM1XHVjNzU4IFx1YzIxOFx1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjRcdWIyOTQgTig0Jm5ic3A7JmxlOyBOICZsZTsgMjAsMDAwKVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjJlNFx1Yzc0Y1x1Yzc0MCBcdWJhODcgXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMCBcdWFjNzhcdWNjZDAgXHVjNTQ0XHViNzk4IFx1YjQ1MCBcdWFjMDBcdWM5YzAgXHVjODg1XHViOTU4XHVjNzU4IFx1YmE4NVx1YjgzOVx1YzViNFx1YWMwMCBcdWI0ZTRcdWM1YjRcdWM2MjhcdWIyZTQuPFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+RSBJICZuZGFzaDsgXHVhZTMwXHVjNWM1IElcdWM2NDAgXHVkNjA0XHVjN2FjIElcdWM3NTggXHVjMTNjXHVkMTMwXHVhZTRjXHVjOWMwXHVjNzU4IFx1YWM3MFx1YjlhY1x1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuJm5ic3A7PFwvbGk+XHJcblx0PGxpPkkgSSBKICZuZGFzaDsgXHVjMTNjXHVkMTMwIElcdWI5N2MgXHVhZTMwXHVjNWM1IEpcdWM1ZDAgXHVjNWYwXHVhY2IwXHVkNTVjXHViMmU0LjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjhcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHViMDVkXHVjNWQwXHViMjk0IFx1YjJlOFx1YzViNCBPXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4mbmJzcDs8c3BhbiBzdHlsZT1cImZvbnQtZmFtaWx5OkFyaWFsLCZxdW90O0hlbHZldGljYSBOZXVlJnF1b3Q7LEhlbHZldGljYSxUYWhvbWEsc2Fucy1zZXJpZlwiPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjhcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDBcdWMxMWMgXHViYTg1XHViODM5XHVjNWI0XHVjNzU4IFx1Y2QxZCBcdWFjMWNcdWMyMThcdWIyOTQgMjAwLDAwMFx1YWMxY1x1Yjk3YyBcdWIxMThcdWM5YzAgXHVjNTRhXHVjNzNjXHViYTcwLCBcdWFkZjhcdWM5MTEgSSBcdWJhODVcdWI4MzlcdWM1YjRcdWM3NTggXHVhYzFjXHVjMjE4XHViMjk0IE5cdWFjMWNcdWJjZjRcdWIyZTQgXHVjNzkxXHViMmU0LjxcL3NwYW4+PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+RSBcdWJhODVcdWI4MzlcdWM1YjRcdWFjMDAgXHViNGU0XHVjNWI0XHVjNjJjIFx1YjU0Y1x1YjljOFx1YjJlNCBcdWQ1NWMgXHVjOTA0XHVjNWQwIFx1ZDU3NFx1YjJmOSBcdWFjNzBcdWI5YWNcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjM3ODAiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJDb3Jwb3JhdGl2ZSBOZXR3b3JrIiwiZGVzY3JpcHRpb24iOiI8cD5BIHZlcnkgYmlnIGNvcnBvcmF0aW9uIGlzIGRldmVsb3BpbmcgaXRzIGNvcnBvcmF0aXZlIG5ldHdvcmsuIEluIHRoZSBiZWdpbm5pbmcgZWFjaCBvZiB0aGUgTiBlbnRlcnByaXNlcyBvZiB0aGUgY29ycG9yYXRpb24sIG51bWVyYXRlZCBmcm9tIDEgdG8gTiwgb3JnYW5pemVkIGl0cyBvd24gY29tcHV0aW5nIGFuZCB0ZWxlY29tbXVuaWNhdGlvbiBjZW50ZXIuIFNvb24sIGZvciBhbWVsaW9yYXRpb24gb2YgdGhlIHNlcnZpY2VzLCB0aGUgY29ycG9yYXRpb24gc3RhcnRlZCB0byBjb2xsZWN0IHNvbWUgZW50ZXJwcmlzZXMgaW4gY2x1c3RlcnMsIGVhY2ggb2YgdGhlbSBzZXJ2ZWQgYnkgYSBzaW5nbGUgY29tcHV0aW5nIGFuZCB0ZWxlY29tbXVuaWNhdGlvbiBjZW50ZXIgYXMgZm9sbG93LiBUaGUgY29ycG9yYXRpb24gY2hvc2Ugb25lIG9mIHRoZSBleGlzdGluZyBjZW50ZXJzIEkgKHNlcnZpbmcgdGhlIGNsdXN0ZXIgQSkgYW5kIG9uZSBvZiB0aGUgZW50ZXJwcmlzZXMgSiBpbiBzb21lIG90aGVyIGNsdXN0ZXIgQiAobm90IG5lY2Vzc2FyaWx5IHRoZSBjZW50ZXIpIGFuZCBsaW5rIHRoZW0gd2l0aCB0ZWxlY29tbXVuaWNhdGlvbiBsaW5lLiBUaGUgbGVuZ3RoIG9mIHRoZSBsaW5lIGJldHdlZW4gdGhlIGVudGVycHJpc2VzIEkgYW5kIEogaXMgfEkgJm5kYXNoOyBKfChtb2QgMTAwMCkuIEluIHN1Y2ggYSB3YXkgdGhlIHR3byBvbGQgY2x1c3RlcnMgYXJlIGpvaW5lZCBpbiBhIG5ldyBjbHVzdGVyLCBzZXJ2ZWQgYnkgdGhlIGNlbnRlciBvZiB0aGUgb2xkIGNsdXN0ZXIgQi4gVW5mb3J0dW5hdGVseSBhZnRlciBlYWNoIGpvaW4gdGhlIHN1bSBvZiB0aGUgbGVuZ3RocyBvZiB0aGUgbGluZXMgbGlua2luZyBhbiBlbnRlcnByaXNlIHRvIGl0cyBzZXJ2aW5nIGNlbnRlciBjb3VsZCBiZSBjaGFuZ2VkIGFuZCB0aGUgZW5kIHVzZXJzIHdvdWxkIGxpa2UgdG8ga25vdyB3aGF0IGlzIHRoZSBuZXcgbGVuZ3RoLiBXcml0ZSBhIHByb2dyYW0gdG8ga2VlcCB0cmFjZSBvZiB0aGUgY2hhbmdlcyBpbiB0aGUgb3JnYW5pemF0aW9uIG9mIHRoZSBuZXR3b3JrIHRoYXQgaXMgYWJsZSBpbiBlYWNoIG1vbWVudCB0byBhbnN3ZXIgdGhlIHF1ZXN0aW9ucyBvZiB0aGUgdXNlcnMuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5Zb3VyIHByb2dyYW0gaGFzIHRvIGJlIHJlYWR5IHRvIHNvbHZlIG1vcmUgdGhhbiBvbmUgdGVzdCBjYXNlLiBUaGUgZmlyc3QgbGluZSBvZiB0aGUgaW5wdXQgZmlsZSB3aWxsIGNvbnRhaW5zIG9ubHkgdGhlIG51bWJlciBUIG9mIHRoZSB0ZXN0IGNhc2VzLiBFYWNoIHRlc3Qgd2lsbCBzdGFydCB3aXRoIHRoZSBudW1iZXIgTiBvZiBlbnRlcnByaXNlcyAoNSZsZTtOJmxlOzIwMDAwKS4gVGhlbiBzb21lIG51bWJlciBvZiBsaW5lcyAobm8gbW9yZSB0aGFuIDIwMDAwMCkgd2lsbCBmb2xsb3cgd2l0aCBvbmUgb2YgdGhlIGNvbW1hbmRzOjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPkUgSSAmbmRhc2g7IGFza2luZyB0aGUgbGVuZ3RoIG9mIHRoZSBwYXRoIGZyb20gdGhlIGVudGVycHJpc2UgSSB0byBpdHMgc2VydmluZyBjZW50ZXIgaW4gdGhlIG1vbWVudDsmbmJzcDs8XC9saT5cclxuXHQ8bGk+SSBJIEogJm5kYXNoOyBpbmZvcm1pbmcgdGhhdCB0aGUgc2VydmluZyBjZW50ZXIgSSBpcyBsaW5rZWQgdG8gdGhlIGVudGVycHJpc2UgSi48XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5UaGUgdGVzdCBjYXNlIGZpbmlzaGVzIHdpdGggYSBsaW5lIGNvbnRhaW5pbmcgdGhlIHdvcmQgTy4gVGhlIEkgY29tbWFuZHMgYXJlIGxlc3MgdGhhbiBOLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlRoZSBvdXRwdXQgc2hvdWxkIGNvbnRhaW4gYXMgbWFueSBsaW5lcyBhcyB0aGUgbnVtYmVyIG9mIEUgY29tbWFuZHMgaW4gYWxsIHRlc3QgY2FzZXMgd2l0aCBhIHNpbmdsZSBudW1iZXIgZWFjaCAmbmRhc2g7IHRoZSBhc2tlZCBzdW0gb2YgbGVuZ3RoIG9mIGxpbmVzIGNvbm5lY3RpbmcgdGhlIGNvcnJlc3BvbmRpbmcgZW50ZXJwcmlzZSB3aXRoIGl0cyBzZXJ2aW5nIGNlbnRlci48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

ACM-ICPC > Regionals > Europe > Southeastern European Regional Contest > SEERC 2004 B번

  • 문제를 번역한 사람: Acka
  • 잘못된 조건을 찾은 사람: kb6912