Submission #102461

#	Time	Username	Problem	Language	Result	Execution time	Memory
102461		BanFcc	Praktični (COCI18_prakticni)	C++14	130 / 130	190 ms	12944 KiB

parkticni

#include<bits/stdc++.h>
#define mp make_pair
#define fi first
#define se second
#define debug(x) cerr<<#x<<" = "<<(x)<<endl
#define eps 1e-8
#define pi acos(-1.0)
using namespace std;
void test(){cerr<<"\n";}
template<typename T,typename... Args>void test(T x,Args... args){cerr<<x<<" ";test(args...);}
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int MAXN=(int)1e5+5;
const int MOD=(int)1e9+7;
struct edge{
    int to,w,nxt;
}ed[MAXN*2];
int head[MAXN],cnt;
void addedge(int u,int v,int w){
    ed[cnt]={v,w,head[u]};
    head[u]=cnt++;
}
int val[MAXN];
bool vis[MAXN],ef[MAXN];
vector<pii>ve,vi;
vector<int>ans[35];
int a[35],p[35];
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    fill(head+1,head+1+n,-1);
    for(int i=1;i<=m;i++){
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        addedge(u,v,w);
        addedge(v,u,w);
    }
    queue<int>q;
    vis[1]=1;
    q.push(1);
    while(!q.empty()){
        int u=q.front();q.pop();
        for(int i=head[u];i!=-1;i=ed[i].nxt){
            if(ef[i/2])continue;
            ef[i/2]=1;
            int v=ed[i].to,w=ed[i].w;
            if(!vis[v]){
                q.push(v);
                vis[v]=1;
                val[v]=val[u]^w;
            }
            else ve.push_back({w,i});
        }
    }
    int num=0;
    for(auto e:ve){
        int u=ed[e.se].to,v=ed[e.se^1].to,w=ed[e.se].w;
        int nd=val[u]^val[v]^w;
        if(nd){
            vi.push_back({nd,e.se/2+1});
            for(int i=30;i>=0;i--){
                if(!(nd>>i)&1)continue;
                if(!a[i]){
                    a[i]=nd;
                    num++;
                    break;
                }
                nd^=a[i];
            }
        }
    }
    for(auto p:vi){
        for(int i=30;i>=0;i--){
            if(p.fi&(1<<i)){
                ans[i].push_back(p.se);
                p.fi^=a[i];
            }
        }
    }
    printf("%d\n",num);
    for(int i=0;i<=30;i++){
        if(a[i]){
            printf("%d %d",a[i],(int)ans[i].size());
            sort(ans[i].begin(),ans[i].end());
            for(auto x:ans[i])printf(" %d",x);
            printf("\n");
        }
    }

    return 0;
}

Compilation message (stderr)

parkticni.cpp: In function 'int main()':
parkticni.cpp:32:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d",&n,&m);
     ~~~~~^~~~~~~~~~~~~~
parkticni.cpp:36:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d",&u,&v,&w);
         ~~~~~^~~~~~~~~~~~~~~~~~~

• Subtask 1: 13 / 13
• Subtask 2: 13 / 13
• Subtask 3: 13 / 13
• Subtask 4: 13 / 13
• Subtask 5: 13 / 13
• Subtask 6: 13 / 13
• Subtask 7: 13 / 13
• Subtask 8: 13 / 13
• Subtask 9: 13 / 13
• Subtask 10: 13 / 13