oj.uz

Submission #102461

# Submission time Handle Problem Language Result Execution time Memory
102461 2019-03-25T06:40:12 Z BanFcc Praktični (COCI18_prakticni) C++14
130 / 130
 190 ms 12944 KB 
#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

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.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 3064 KB Output is correct
2 Correct 26 ms 3064 KB Output is correct
3 Correct 12 ms 1152 KB Output is correct
4 Correct 8 ms 896 KB Output is correct
5 Correct 64 ms 5496 KB Output is correct
6 Correct 93 ms 5516 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 1664 KB Output is correct
2 Correct 14 ms 1792 KB Output is correct
3 Correct 16 ms 2048 KB Output is correct
4 Correct 21 ms 2296 KB Output is correct
5 Correct 84 ms 5572 KB Output is correct
6 Correct 33 ms 3576 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 4016 KB Output is correct
2 Correct 50 ms 5016 KB Output is correct
3 Correct 2 ms 384 KB Output is correct

Subtask #4
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 5368 KB Output is correct
2 Correct 119 ms 10152 KB Output is correct
3 Correct 4 ms 512 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 4472 KB Output is correct
2 Correct 49 ms 5112 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 7716 KB Output is correct
2 Correct 49 ms 3448 KB Output is correct

Subtask #7
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 6080 KB Output is correct
2 Correct 126 ms 9444 KB Output is correct
3 Correct 56 ms 5112 KB Output is correct

Subtask #8
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 9624 KB Output is correct
2 Correct 190 ms 12944 KB Output is correct
3 Correct 144 ms 11276 KB Output is correct

Subtask #9
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 2304 KB Output is correct
2 Correct 32 ms 2904 KB Output is correct
3 Correct 78 ms 7032 KB Output is correct

Subtask #10
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 6904 KB Output is correct
2 Correct 49 ms 4292 KB Output is correct
3 Correct 185 ms 10360 KB Output is correct