Submission #527834


Source Code Expand

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

struct BIT{
    int N;
    vector<int>bit;
    void init(int n){
        N=n;
        bit.resize(N,0);
    }
    void inc(int k){
        for(k++;k<=N;k+=k&-k)bit[k]++;
    }
    void dec(int k){
        for(k++;k<=N;k+=k&-k)bit[k]--;
    }
    int sum(int k){
        int ret=0;
        for(k++;k;k-=k&-k)ret+=bit[k];
        return ret;
    }
};

struct UF{
    int N;
    vector<int>par,sz;
    void init(int n){
        N=n;
        par.resize(N);
        sz.resize(N,1);
        for(int i=0;i<N;i++)par[i]=i;
    }
    int find(int x){
        return x==par[x]?x:par[x]=find(par[x]);
    }
    void unite(int x,int y){
        x=find(x);y=find(y);
        if(x==y)return;
        if(sz[x]<sz[y])swap(x,y);
        par[y]=x;
        sz[x]+=sz[y];
    }
    bool same(int x,int y){
        return find(x)==find(y);
    }
};

vector<int>G[100000];
bool used[100000];
BIT bit;
set<pair<int,int> >S;


int solve(vector<int>&vec){
    int ret=0;
    for(int i=0;i<vec.size();i++){
        ret+=i-bit.sum(vec[i]-1);
        bit.inc(vec[i]);
    }
    for(int i=0;i<vec.size();i++){
        bit.dec(vec[i]);
    }
    return ret;
}


int best_swap(signed N, signed M,signed E[][2]){
    for(int i=0;i<M;i++){
        int a=E[i][0],b=E[i][1];
        G[a].push_back(b);
        G[b].push_back(a);
    }

    for(int i=0;i<N;i++){
        sort(G[i].begin(),G[i].end());
        G[i].erase(unique(G[i].begin(),G[i].end()),G[i].end());
    }

    UF uf;uf.init(N);
    for(int i=0;i<M;i++){
        int a=E[i][0],b=E[i][1];
        if(S.find(pair<int,int>(min(a,b),max(a,b)))!=S.end())continue;
        if(uf.same(a,b))return -1;
        uf.unite(a,b);
        S.insert(pair<int,int>(min(a,b),max(a,b)));
    }

    for(int i=0;i<N;i++){
        if(G[i].size()>2)return -1;
    }

    int ans=0;
    bit.init(N);
    return ans;
}
/*
int N,M,E[100000][2];
signed main(){
    cin>>N>>M;
    for(int i=0;i<M;i++){
        int a,b;
        cin>>a>>b;
        E[i][0]=a;E[i][1]=b;
    }


    cout<<best_swap(N,M,E)<<endl;

    return 0;
}
*/

Submission Info

Submission Time
Task A - 国際道迷いオリンピック(International Michimayoi Olympic)
User latte0119
Language IOI-Style C++ (GCC 5.4.1)
Score 0
Code Size 2212 Byte
Status WA
Exec Time 328 ms
Memory 19488 KB

Judge Result

Set Name Subtask1 Subtask2 Subtask3
Score / Max Score 0 / 10 0 / 44 0 / 46
Status
AC × 1
WA × 6
AC × 1
WA × 12
AC × 5
WA × 17
Set Name Test Cases
Subtask1 subtask1/1, subtask1/2, subtask1/3, subtask1/4, subtask1/5, subtask1/6, subtask1/7
Subtask2 subtask1/1, subtask1/2, subtask1/3, subtask1/4, subtask1/5, subtask1/6, subtask1/7, subtask2/1, subtask2/2, subtask2/3, subtask2/4, subtask2/5, subtask2/6
Subtask3 subtask1/1, subtask1/2, subtask1/3, subtask1/4, subtask1/5, subtask1/6, subtask1/7, subtask2/1, subtask2/2, subtask2/3, subtask2/4, subtask2/5, subtask2/6, subtask3/1, subtask3/2, subtask3/3, subtask3/4, subtask3/5, subtask3/6, subtask3/7, subtask3/8, subtask3/9
Case Name Status Exec Time Memory
subtask1/1 WA 35 ms 3352 KB
subtask1/2 WA 31 ms 3352 KB
subtask1/3 WA 33 ms 3352 KB
subtask1/4 WA 33 ms 3348 KB
subtask1/5 WA 34 ms 3476 KB
subtask1/6 WA 35 ms 3472 KB
subtask1/7 AC 34 ms 3432 KB
subtask2/1 WA 41 ms 3980 KB
subtask2/2 WA 63 ms 5844 KB
subtask2/3 WA 154 ms 12632 KB
subtask2/4 WA 202 ms 15828 KB
subtask2/5 WA 204 ms 15840 KB
subtask2/6 WA 203 ms 15828 KB
subtask3/1 AC 61 ms 5328 KB
subtask3/2 AC 99 ms 8272 KB
subtask3/3 WA 81 ms 8280 KB
subtask3/4 WA 107 ms 9952 KB
subtask3/5 AC 208 ms 14992 KB
subtask3/6 WA 255 ms 16524 KB
subtask3/7 WA 316 ms 18572 KB
subtask3/8 WA 328 ms 19488 KB
subtask3/9 AC 39 ms 5716 KB