結果
| 問題 | No.416 旅行会社 |
| ユーザー |
 紙ぺーぱー
|
| 提出日時 | 2016-08-27 00:43:02 |
| 言語 | C#(csc) (csc 3.9.0) |
| 結果 |
AC
|
| 実行時間 | 934 ms / 4,000 ms |
| コード長 | 8,664 bytes |
| コンパイル時間 | 3,883 ms |
| コンパイル使用メモリ | 110,592 KB |
| 実行使用メモリ | 51,188 KB |
| 最終ジャッジ日時 | 2024-05-08 15:03:38 |
| 合計ジャッジ時間 | 10,329 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge4 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 411 ms
45,556 KB |
| testcase_01 | AC | 27 ms
18,944 KB |
| testcase_02 | AC | 27 ms
19,072 KB |
| testcase_03 | AC | 27 ms
19,200 KB |
| testcase_04 | AC | 28 ms
18,944 KB |
| testcase_05 | AC | 29 ms
19,072 KB |
| testcase_06 | AC | 29 ms
18,688 KB |
| testcase_07 | AC | 29 ms
19,200 KB |
| testcase_08 | AC | 34 ms
19,584 KB |
| testcase_09 | AC | 69 ms
21,008 KB |
| testcase_10 | AC | 438 ms
45,684 KB |
| testcase_11 | AC | 384 ms
45,684 KB |
| testcase_12 | AC | 375 ms
45,056 KB |
| testcase_13 | AC | 385 ms
45,688 KB |
| testcase_14 | AC | 934 ms
50,928 KB |
| testcase_15 | AC | 731 ms
50,932 KB |
| testcase_16 | AC | 706 ms
50,796 KB |
| testcase_17 | AC | 743 ms
51,188 KB |
| testcase_18 | AC | 812 ms
50,924 KB |
| testcase_19 | AC | 576 ms
44,416 KB |
| testcase_20 | AC | 562 ms
44,672 KB |
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc) Copyright (C) Microsoft Corporation. All rights reserved.
ソースコード
using System;
using System.Linq;
using System.Linq.Expressions;
using System.Collections.Generic;
using Debug = System.Diagnostics.Debug;
using StringBuilder = System.Text.StringBuilder;
using System.Numerics;
using Number = System.Int64;
namespace Program
{
public class Solver
{
public void Solve()
{
var n = sc.Integer();
var m = sc.Integer();
var q = sc.Integer();
var a = new int[m];
var b = new int[m];
for (int i = 0; i < m; i++)
{
a[i] = sc.Integer() - 1;
b[i] = sc.Integer() - 1;
if (a[i] > b[i]) Swap(ref a[i], ref b[i]);
}
var use = new SortedSet<long>();
var c = new int[q];
var d = new int[q];
for (int i = 0; i < q; i++)
{
c[i] = sc.Integer() - 1;
d[i] = sc.Integer() - 1;
if (c[i] > d[i]) Swap(ref c[i], ref d[i]);
use.Add(c[i] * 1000000L + d[i]);
}
var set = new LimitedPersistentDisjointSet(n);
for (int i = 0; i < m; i++)
if (!use.Contains(a[i] * 1000000L + b[i])) set.Unite(a[i], b[i], 0);
for (int i = q - 1; i >= 0; i--)
set.Unite(c[i], d[i], q - i);
for (int i = 1; i < n; i++)
{
if (set.IsUnited(0, 0, i))
{
IO.Printer.Out.WriteLine(-1);
continue;
}
if (!set.IsUnited(q, 0, i))
{
IO.Printer.Out.WriteLine(0);
continue;
}
var l = 0; var r = q;
while (l + 1 < r)
{
var x = (l + r) / 2;
if (set.IsUnited(x, 0, i)) r = x;
else l = x;
}
IO.Printer.Out.WriteLine(q - l);
}
}
public IO.StreamScanner sc = new IO.StreamScanner(Console.OpenStandardInput());
static T[] Enumerate<T>(int n, Func<int, T> f) { var a = new T[n]; for (int i = 0; i < n; ++i) a[i] = f(i); return a; }
static public void Swap<T>(ref T a, ref T b) { var tmp = a; a = b; b = tmp; }
}
}
#region main
static class Ex
{
static public string AsString(this IEnumerable<char> ie) { return new string(System.Linq.Enumerable.ToArray(ie)); }
static public string AsJoinedString<T>(this IEnumerable<T> ie, string st = " ") { return string.Join(st, ie); }
static public void Main()
{
var solver = new Program.Solver();
solver.Solve();
Program.IO.Printer.Out.Flush();
}
}
#endregion
#region Ex
namespace Program.IO
{
using System.IO;
using System.Text;
using System.Globalization;
public class Printer: StreamWriter
{
static Printer() { Out = new Printer(Console.OpenStandardOutput()) { AutoFlush = false }; }
public static Printer Out { get; set; }
public override IFormatProvider FormatProvider { get { return CultureInfo.InvariantCulture; } }
public Printer(System.IO.Stream stream) : base(stream, new UTF8Encoding(false, true)) { }
public Printer(System.IO.Stream stream, Encoding encoding) : base(stream, encoding) { }
public void Write<T>(string format, T[] source) { base.Write(format, source.OfType<object>().ToArray()); }
public void WriteLine<T>(string format, T[] source) { base.WriteLine(format, source.OfType<object>().ToArray()); }
}
public class StreamScanner
{
public StreamScanner(Stream stream) { str = stream; }
public readonly Stream str;
private readonly byte[] buf = new byte[1024];
private int len, ptr;
public bool isEof = false;
public bool IsEndOfStream { get { return isEof; } }
private byte read()
{
if (isEof) return 0;
if (ptr >= len) { ptr = 0; if ((len = str.Read(buf, 0, 1024)) <= 0) { isEof = true; return 0; } }
return buf[ptr++];
}
public char Char() { byte b = 0; do b = read(); while ((b < 33 || 126 < b) && !isEof); return (char)b; }
public string Scan()
{
var sb = new StringBuilder();
for (var b = Char(); b >= 33 && b <= 126; b = (char)read())
sb.Append(b);
return sb.ToString();
}
public string ScanLine()
{
var sb = new StringBuilder();
for (var b = Char(); b != '\n'; b = (char)read())
if (b == 0) break;
else if (b != '\r') sb.Append(b);
return sb.ToString();
}
public long Long()
{
if (isEof) return long.MinValue;
long ret = 0; byte b = 0; var ng = false;
do b = read();
while (b != 0 && b != '-' && (b < '0' || '9' < b));
if (b == 0) return long.MinValue;
if (b == '-') { ng = true; b = read(); }
for (; true; b = read())
{
if (b < '0' || '9' < b)
return ng ? -ret : ret;
else ret = ret * 10 + b - '0';
}
}
public int Integer() { return (isEof) ? int.MinValue : (int)Long(); }
public double Double() { var s = Scan(); return s != "" ? double.Parse(s, CultureInfo.InvariantCulture) : double.NaN; }
private T[] enumerate<T>(int n, Func<T> f)
{
var a = new T[n];
for (int i = 0; i < n; ++i) a[i] = f();
return a;
}
public char[] Char(int n) { return enumerate(n, Char); }
public string[] Scan(int n) { return enumerate(n, Scan); }
public double[] Double(int n) { return enumerate(n, Double); }
public int[] Integer(int n) { return enumerate(n, Integer); }
public long[] Long(int n) { return enumerate(n, Long); }
}
}
#endregion
#region Limited Persistent data structure
/// <summary>
/// 部分永続性だけを持ったdisjoint set
/// </summary>
public class LimitedPersistentDisjointSet
{
int n;
FastList<pair>[] history;
byte[] rank;
int[] par;
int last = 0;
public LimitedPersistentDisjointSet(int N)
{
n = N;
history = new FastList<pair>[n];
rank = new byte[n];
par = new int[n];
for (int i = 0; i < n; i++)
{
par[i] = -1;
history[i] = new FastList<pair>(); history[i].Add(new pair(0, -1));
}
}
/// <summary>
/// (u,size(u))を返す
/// </summary>
public KeyValuePair<int, int> Get(int time, int x)
{
var l = 0;
int r = history[x].Count;
if (history[x].data[r - 1].v >= 0 && history[x].data[r - 1].t <= time) return Get(time, history[x].data[r - 1].v);
while (l + 1 < r)
{
var m = (l + r) / 2;
if (history[x].data[m].t <= time) l = m;
else r = m;
}
if (history[x].data[l].v < 0) return new KeyValuePair<int, int>(x, -history[x].data[l].v);
else return Get(time, history[x].data[l].v);
}
int _get(int x)
{
if (par[x] < 0) return x;
else return par[x] = _get(par[x]);
}
public bool Unite(int x, int y, int time)
{
x = _get(x);
y = _get(y);
last = time;
if (x == y) return false;
if (rank[x] < rank[y])
{
par[y] += par[x];
par[x] = y;
}
else
{
par[x] += par[y];
par[y] = x;
if (rank[x] == rank[y])
rank[x]++;
}
history[x].Add(new pair(last, par[x]));
history[y].Add(new pair(last, par[y]));
return true;
}
public bool IsUnited(int time, int x, int y)
{
return Get(time, x).Key == Get(time, y).Key;
}
struct pair
{
public int t, v;
public pair(int time, int value)
{
t = time; v = value;
}
}
public class FastList<T>
{
const int SIZE = 8;
public T[] data;
public int Count { get { return size; } }
int size;
public FastList() { data = new T[SIZE]; }
public void Resize()
{
var ndata = new T[data.Length << 1];
Array.Copy(data, ndata, size);
data = ndata;
}
public void Add(T item)
{
if (size == data.Length) Resize();
data[size++] = item;
}
}
}
#endregion