Submission #1147464

#	Time	Username	Problem	Language	Result	Execution time	Memory
1147464		Luvidi	Rigged Roads (NOI19_riggedroads)	C++20	0 / 100	284 ms	327680 KiB

riggedroads

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pll pair<ll, ll>
#define pii pair<int, int>
#define fs first
#define sc second
#define pb push_back

const int maxn=3e5;
vector<pii> adj[maxn+1];
int d[maxn+1];
pii p[maxn+1];

void dfs(int v){
    for(auto[u,i]:adj[v])if(u!=p[v].fs){
        d[u]=d[v]+1;
        p[u]={v,i};
        dfs(u);
    }
}

void solve() {
    int n,m;
    cin>>n>>m;
    pii e[m+1];
    for(int i=1;i<=m;i++)cin>>e[i].fs>>e[i].sc;
    bool s[m+1];
    memset(s,-1,sizeof(s));
    for(int i=0;i<n-1;i++){
        int x;
        cin>>x;
        s[x]=1;
        adj[e[x].fs].pb({e[x].sc,x});
        adj[e[x].sc].pb({e[x].fs,x});
    }
    dfs(1);
    bool a[m+1][m+1];
    memset(a,1,sizeof(a));
    for(int i=1;i<=m;i++){
        int x=1;
        if(!s[i]){
            auto[u,v]=e[i];
            vector<int> pt;
            while(u!=v){
                if(d[u]>d[v]){
                    pt.pb(p[u].sc);
                    u=p[u].fs;
                }else{
                    pt.pb(p[v].sc);
                    v=p[v].fs;
                }
            }
            bool b[pt.size()];
            memset(b,1,sizeof(b));
            vector<int> vl;
            int c=pt.size();
            while(c){
                int idx=-1;
                for(int j=0;j<pt.size();j++)if(b[j]&&a[pt[j]][x])idx=j;
                if(idx!=-1){
                    b[idx]=0;
                    vl.pb(x);
                    c--;
                }
                x++;
            }
            bool ip[m+1],iv[m+1];
            memset(ip,0,sizeof(ip));
            memset(iv,0,sizeof(iv));
            for(int i:pt)ip[i]=1;
            for(int i:vl)iv[i]=1;
            for(int i=1;i<=m;i++){
                for(int j=1;j<=m;j++)if(ip[i]^iv[j])a[i][j]=0;
            }
        }
        while(!a[i][x])x++;
        assert(x<=m);
        for(int j=1;j<=m;j++)if(j!=x)a[i][j]=0;
        for(int j=1;j<=m;j++)if(j!=i)a[j][x]=0;
        cout<<x<<' ';
    }
    cout<<'\n';
}

int main() {
    #ifdef FPO
        freopen("in","r",stdin);
        freopen("out","w",stdout);
    #endif
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    solve();
}

• Subtask 1: 0 / 8
• Subtask 2: 0 / 19
• Subtask 3: 0 / 9
• Subtask 4: 0 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 12
• Subtask 7: 0 / 32