結果

問題 No.416 旅行会社
ユーザー vjudge1
提出日時 2024-12-23 21:18:41
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 296 ms / 4,000 ms
コード長 2,409 bytes
コンパイル時間 6,524 ms
コンパイル使用メモリ 314,912 KB
実行使用メモリ 27,404 KB
最終ジャッジ日時 2024-12-23 21:18:53
合計ジャッジ時間 10,372 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

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=2e5+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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0