結果

問題 No.416 旅行会社
ユーザー vjudge1vjudge1
提出日時 2024-12-23 21:14:02
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 2,409 bytes
コンパイル時間 5,729 ms
コンパイル使用メモリ 314,916 KB
実行使用メモリ 19,048 KB
最終ジャッジ日時 2024-12-23 21:14:12
合計ジャッジ時間 8,484 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 84 ms
18,780 KB
testcase_01 AC 2 ms
5,248 KB
testcase_02 AC 3 ms
5,248 KB
testcase_03 AC 3 ms
5,248 KB
testcase_04 AC 3 ms
5,248 KB
testcase_05 AC 2 ms
5,248 KB
testcase_06 AC 2 ms
5,248 KB
testcase_07 AC 3 ms
5,248 KB
testcase_08 AC 5 ms
5,248 KB
testcase_09 AC 14 ms
5,248 KB
testcase_10 AC 111 ms
18,652 KB
testcase_11 AC 111 ms
19,048 KB
testcase_12 AC 116 ms
19,044 KB
testcase_13 AC 86 ms
19,028 KB
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

/*
*Author: Hughpig
*made in China
*/

#include<bits/stdc++.h>
using namespace std;
#if __has_include(<atcoder/all>)
#include<atcoder/all>
using namespace atcoder;
#endif
#define ll long long
#define ld long double
#define up(l,r,i) for(int i=(l);(i)<=(r);++i)
#define vi vector<ll>
#define pii pair<ll,ll>
#define pb push_back
#define pob pop_back
#define gc getchar
#define pc putchar
#define il inline
#define all(x) x.begin(),x.end()
#define reg register
#define loop while(1)
#define debug cout<<"QwQ\n"
#define Sort(a) sort(a.begin(), a.end())

void file(string fl) {
	freopen((fl+".in").c_str(),"r",stdin);
	freopen((fl+".out").c_str(),"w",stdout);
}

il ll read()
{
    char ch=gc();
    ll s=0,w=1;
    while(ch<'0'||ch>'9')
    {
        if(ch=='-'){w=-1;}
        ch=gc();
    }
    while(ch>='0'&&ch<='9')
    {
        s=(s<<1)+(s<<3)+ch-48;
        ch=gc();
    }
    return w*s;
}

il void write(ll x)
{
	if(x<0)
	{
		putchar('-');
		x=-x;
	}
	if(x>9)write(x/10);
	putchar(x%10+'0');
}

ll ksm(ll a,ll b,ll p)
{
	ll ans=1%p;
	for(;b;b>>=1){
		if(b&1) ans=ans*a%p;
		a=a*a%p;
	}
	return ans;
}

void ios_optimize(){ios::sync_with_stdio(0);cin.tie(0);}
ll ls(ll u){return u<<1;}
ll rs(ll u){return u<<1|1;}
ll myabs(ll x){return x>0?x:-x;}
ll mymax(ll x,ll y){return x>y?x:y;}
ll mymin(ll x,ll y){return x<y?x:y;}
ll lowbit(ll n){return n&-n;}
ll gcd(ll x,ll y){return y?gcd(y,x%y):x;}
ll lcm(ll x,ll y){return x/gcd(x,y)*y;}
ll inv(ll a,ll p){return ksm(a,p-2,p);}
void yn(bool f){cout<<(f?"Yes\n":"No\n");}

constexpr int N=1e5+9;
constexpr int mod1=998244353,mod2=1e9+7;
constexpr int inf=1e9;
constexpr ll INF=1e18;
constexpr double eps=1e-9;

ll n,m,q,u[N],v[N],u_[N],v_[N],fa[N],ans[N];
set<pair<int,int> > vis;
vector<int> G[N];

void merge(int x,int y,int k){
	x=fa[x],y=fa[y];
	if(x==y)return;
	if((x>1&&G[x].size()<G[y].size())||y==1)swap(x,y);
	for(auto son:G[y]){
		fa[son]=x;
		G[x].pb(son);
	}
	if(x==1)for(auto son:G[y])ans[son]=k;
	G[y].clear();
}

int main()
{
	ios_optimize();
    int TestCases=1;
    //cin>>TestCases;
    while(TestCases--){
		cin>>n>>m>>q;
		up(1,n,i)fa[i]=i,G[i].pb(i);
		up(1,m,i){
			cin>>u[i]>>v[i];
		}
		up(1,q,i){
			cin>>u_[i]>>v_[i];
			vis.insert({u_[i],v_[i]});
		}
		up(1,m,i){
			if(!vis.count({u[i],v[i]}))merge(u[i],v[i],-1);
		}
		for(int i=q;i;--i){
			merge(u_[i],v_[i],i);
		}
		for(int i=2;i<=n;++i)cout<<ans[i]<<'\n';
    }
	return 0;
}
0