Submission #1361219

#	Time	Username	Problem	Language	Result	Execution time	Memory
1361219		farica	Tour (BOI25_tou)	C++17	100 / 100	425 ms	168760 KiB

Main

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

struct Edge{
    Edge(int t,int w,int i){
        to=t;
        val=w;
        live=true;
        check=false;
        id=i;
    }
    int to;
    int val;
    int id;
    bool live;
    bool check;
};

vector<vector<Edge>> g;
vector<int> state;
stack<int> stk;

bool dfs(int u,int r){
    if(state[u]==-1||state[u]==r){
        return false;
    }
    bool tmp;
    for(int i=0;i<g[u].size();i++){
        if(!g[u][i].live){
            continue;
        }
        if(g[u][i].val==r){
            continue;
        }
        stk.push(g[u][i].id);
        if(g[u][i].check){
            return true;
        }
        g[u][i].check=true;
        tmp=dfs(g[u][i].to,g[u][i].val);
        g[u][i].check=false;
        if(tmp){
            return true;
        }
        stk.pop();
        g[u][i].live=false;
    }
    if(state[u]==0){
        state[u]=r;
    }else{
        state[u]=-1;
    }
    return false;
}

int n,m,x,y,w,start,now,k;
Edge tmpedge=Edge(0,0,0);
vector<int> res;

void solve(){
    scanf("%d%d",&n,&m);
    g.clear();
    state.clear();
    res.clear();
    while(!stk.empty()){
        stk.pop();
    }
    for(int i=0;i<n;i++){
        state.push_back(0);
        g.push_back({});
    }
    for(int i=0;i<m;i++){
        scanf("%d%d%d",&x,&y,&w);
        x--;
        y--;
        tmpedge=Edge(y,w,i+1);
        g[x].push_back(tmpedge);
    }
    for(int i=0;i<n;i++){
        if(dfs(i,-1)){
            break;
        }
    }
    if(stk.empty()){
        printf("NO\n");
        return;
    }
    printf("YES\n");
    res.push_back(stk.top());
    stk.pop();
    while(stk.top()!=res[0]){
        res.push_back(stk.top());
        stk.pop();
    }
    printf("%d",res.size());
    for(int i=res.size()-1;i>=0;i--){
        printf(" %d",res[i]);
    }
    printf("\n");
}

int t;

int main(){
    scanf("%d",&t);
    while(t--){
        solve();
    }
}

Compilation message (stderr)

Main.cpp: In function 'void solve()':
Main.cpp:95:14: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wformat=]
   95 |     printf("%d",res.size());
      |             ~^  ~~~~~~~~~~
      |              |          |
      |              int        std::vector<int>::size_type {aka long unsigned int}
      |             %ld
Main.cpp:61:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |     scanf("%d%d",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~
Main.cpp:73:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   73 |         scanf("%d%d%d",&x,&y,&w);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:105:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  105 |     scanf("%d",&t);
      |     ~~~~~^~~~~~~~~

• Subtask 1: 0 / 0
• Subtask 2: 9 / 9
• Subtask 3: 23 / 23
• Subtask 4: 19 / 19
• Subtask 5: 25 / 25
• Subtask 6: 24 / 24