rk:8305
垃圾了这次

4.10

晚上$10:40$进比赛,可能是因为外国比较慢。
A题题目都没怎么看懂语言不通!!!试过谷歌翻译,但是有$LaTeX$所以会乱码,百度翻译也不尽人意。
下午花了$3$个多小时都在写一道毒瘤题,实在看不懂别人写的题解,自己也想不出来,有点烦躁。
前半个小时看了下题,没怎么明白题意就放弃了,但是后面还是滚回来写了。
挺简单的第一题,没什么难度,的确有入门组的感觉。但是还是有一个点没判断到,无情WA。后面还是自己造数据debug回来。
第二题复制到百度翻译也还算看得懂,但是当时我还是懵逼的,半天想不出来怎么解。最后心里默念:我是大佬我是大佬我是大佬我是大佬还是有了一点思路。贪心,优先队列每次取出钱最少的那个崽,正确性自我感觉良好。交上去第四个点错了,以为是类型转换的原因,每个表达式都弄了个*1.0,没什么效果。突然想起来在刚看题的时候自己就意识到过要开$longlong$,最后A了。写完差不多12点了,溜了。话说父母好像不是很反对我通宵打比赛啊

updata 4.11

早上起来又写了俩小时题,代码敲了半天最后总算是完工。还是这道毒瘤,我靠这能写?

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
#include <cstdio>
#include <queue>
using namespace std;
const int maxn=50005;
const int maxm=200005;
const int maxk=100005;
const int maxt=10005;
#define err -1
#define nie cout<<"NIE";return 0;
#define debug cout<<"Test\n";
int read();
///
struct edge{
    int u;
    int v;
    edge(int U,int V):u(U),v(V){};
    edge():u(0),v(0){};
    bool operator < (edge E){
        if(u!=E.u)return u<E.u;
        return v<E.v;
    }
    bool operator == (edge E){
        return u==E.u && v==E.v;
    }
} e[maxm];
vector <int> fr[maxm];
struct frmark{
    vector <int> v;
    vector <int> num;
} mk[maxm];
int n,m,t,k,tote,tot,rd,cnt;
int tmp[maxk],a[maxm];
int vis[maxm];
int bel[maxm];
int cnte[maxn];
int cntg[maxn];
int nxt[maxm],pre[maxm];
stack <int> ans;
vector <int> road[maxt];
///
void add(int U,int V){
    //add(int x,int y,int z){d[x]++,d[y]--;V[++ed]=y;W[ed]=z;NXT[ed]=g[x];g[x]=ed;}
    ++cntg[U];--cntg[V];
    mk[U].v.push_back(V);
    mk[U].num.push_back(tot);
}
int findroad(int u,int v){
    edge k(u,v);
    int l=1,r=m,mid;
    while(l<=r){
        mid=r - ( (r-l) << 1 );
        if(e[mid]==k)return mid;
        if(e[mid]<k)l=mid+1;
        else r=mid-1;
    }
    return err;
}
void dfs(int u){
    for(int i=1;i<=mk[u].v.size();++i){
        if(vis[ mk[u].v[i] ])continue;
        vis[ mk[u].v[i] ] = 1;
        dfs(mk[u].v[i]);
        ans.push(mk[u].num[i]);
    }
}
void print(){
    while(!ans.empty()){
        int id=ans.top();
        ans.pop();
        for(int i=1;i<=fr[id].size();++i){
            cout<<fr[id][i]<<"\n";
        }
    }
}
int main(){
    n=read();m=read();
    for(int i=1;i<=m;++i){
        int u=read();
        int v=read();
        e[++tote]=edge(u,v);
        ++cnte[u];
        --cnte[v];
    }
    for(int i=1;i<=n;++i)
    if(cnte[i])
    printf("cnte[%d]=%d\n",i,cnte[i]);
    sort(e+1,e+m+1);
    t=read();
    for(int j=1;j<=t;++j){
        k=read();
        for(int i=1;i<=k;++i){
            a[i]=read();
            road[j].push_back(a[i]);
        }
        for(int i=1;i<k;++i){
            tmp[i] = findroad(a[i],a[i+1]);
            if(tmp[i]==err)nie
        }
        for(int i=1;i<k-1;++i){
            //如果这条路径的下一条还没被找到过
            //那就给它置为找到过 
            if(!nxt[tmp[i]])nxt[tmp[i]]=tmp[i+1];
            //如果找到过,就看这条路径的nxt/pre和之前找到过的nxt/pre是不是相等
            //不相等,则无解 
            else if(nxt[tmp[i]]!=tmp[i+1])nie
            if(!pre[tmp[i+1]])pre[tmp[i+1]]=tmp[i];
            else if(pre[tmp[i+1]]!=tmp[i])nie
        }
    }
    int k=0,j=0;
    for(int i=1;i<=m;++i){
        if(!pre[i]){
            //如果这条边在路口序列的前一个是空的
            //说明他是一个路口序列的开头或者是非路口序列 
            k=0,j=i;++tot;
            while(j){//当这条路没走到终点
                fr[tot].push_back(j);
                a[++k]=j;
                ++cnt;
                j=nxt[j];
            }
            add(e[i].u,e[a[k]].v);
        }
    }
    if(cnt<m)nie
    for(int i=1;i<=n;++i)
    if(cntg[i])nie
    dfs(1);
    cout<<"TAK\n";
    print();
    return 0;
}

inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch>'9' && ch<'0'){
        if(ch=='-')
        f=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9'){
        x=(x<<3)+(x<<1)+(ch^48);
        ch=getchar();
    }
    return x*f;
}

发表评论

邮箱地址不会被公开。